Selecție CPPI 2024 - Mirror Seniori | Highlight

Cerință

Avem un text format din $n$ caractere. Acestea sunt numerotate de la stânga începând cu poziția $1$. 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 $st$ și $dr$ inclusiv se colorează folosind culoarea $c$ (indiferent dacă era anterior colorat sau nu). Dacă $c = 0$ se consideră că ștergem zona de highlight intre pozițiile $st$ și $dr$ ($0$ nu este culoare)

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

Date de intrare

Pe prima linie a fișierului highlight.in se află $n$ (lungimea textului) și $m$ (numărul de operații). Pe fiecare din următoarele $m$ 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 $2$ 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

• $1 \leq n \leq 100 \ 000$;
• $1 \leq m \leq 100 \ 000$;
• $0 \leq c \leq 100 \ 000$ (pentru operațiile de tip $1$);
• $1 \leq c \leq 100 \ 000$ (pentru operațiile de tip $2$);
• La fiecare operație de tip $1$ valorile $st$ și $dr$ sunt cuprinse între $1$ și $n$ inclusiv și $st \leq dr$;
• Pentru $27$ de puncte, $1 \leq n, m \leq 2 \ 000$;
• Pentru alte $30$ de puncte, $c <= 1$ (pentru operațiile de tipul $1$ și $2$).

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 $1$ roșu si culoarea $2$ albastru.

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