Selecție CPPI 2024 - Mirror Seniori | Highlight

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: highlight.in Output: highlight.out

Cerință

Avem un text format din nn caractere. Acestea sunt numerotate de la stânga începând cu poziția 11. Asupra acestuia se aplică operații de highlight. O operație este specificată printr-un triplet de forma st dr c cu semnificația: Caracterele aflate între pozițiile stst și drdr inclusiv se colorează folosind culoarea cc (indiferent dacă era anterior colorat sau nu). Dacă c=0c = 0 se consideră că ștergem zona de highlight intre pozițiile stst și drdr (00 nu este culoare)

Din când în când ne interesează să aflăm, pentru o culoare cc dată, câte zone sunt highlightate cu ea. O secvență maximală de caractere consecutive care au culoarea cc se numără o singură dată.

Date de intrare

Pe prima linie a fișierului highlight.in se află nn (lungimea textului) și mm (numărul de operații). Pe fiecare din următoarele mm linii se află descrierea câte unei operații în unul din următoarele două moduri:

  • 1 sr dr c (reprezintă o operație de aplicare de highlight așa cum s-a descris mai sus);
  • 2 c (reprezintă o operație de interogare, așa cum s-a descris mai sus).

Date de ieșire

Fișierul highlight.out conține același număr de linii cu numărul de operații de tip 22 din fișierul de intrare. Pentru fiecare operație, în ordinea aparițiilor, se scrie câte un număr, cu semnificația descrisă anterior.

Restricții și precizări

  • 1n100 0001 \leq n \leq 100 \ 000;
  • 1m100 0001 \leq m \leq 100 \ 000;
  • 0c100 0000 \leq c \leq 100 \ 000 (pentru operațiile de tip 11);
  • 1c100 0001 \leq c \leq 100 \ 000 (pentru operațiile de tip 22);
  • La fiecare operație de tip 11 valorile stst și drdr sunt cuprinse între 11 și nn inclusiv și stdrst \leq dr;
  • Pentru 2727 de puncte, 1n,m2 0001 \leq n, m \leq 2 \ 000;
  • Pentru alte 3030 de puncte, c<=1c <= 1 (pentru operațiile de tipul 11 și 22).

Exemplu

highlight.in

9 10
1 3 3 1
1 2 4 1
1 5 6 1
2 1
2 2
1 4 5 2
2 1
1 3 5 0
2 1
2 2

highlight.out

1
0
2
2
0

Explicație

Considerăm culoarea 11 roșu si culoarea 22 albastru.

  • 1 3 3 1: XXXXXXXXXXX\textcolor{red}{X}XXXXXX
  • 1 2 4 1: XXXXXXXXXX\textcolor{red}{XXX}XXXXX
  • 1 5 6 1: XXXXXXXXXX\textcolor{red}{XXXXX}XXX
  • 2 1: Culoarea 11 apare o dată.
  • 2 2: Culoarea 22 apare de zero ori.
  • 1 4 5 2: XXXXXXXXXX\textcolor{red}{XX}\textcolor{blue}{XX}\textcolor{red}{X}XXX
  • 2 1: Culoarea 11 apare de două ori.
  • 1 3 5 0: XXXXXXXXX\textcolor{red}{X}XXX\textcolor{red}{X}XX
  • 2 1: Culoarea 11 apare de două ori.
  • 2 2: Culoarea 22 nu apare.

Log in or sign up to be able to send submissions!