== include(page="template/taskheader" task_id="calin") ==
*Nota 1*: Problema este adaptată după "Stable Market":https://www.codechef.com/problems/SMARKET (Code Chef).
*Nota 2*: Punctajele subtaskurilor diferă de concursul original.
Călin publică un film pe TikTok în care vorbește timp de $n$ minute despre cel mult 9 subiecte. La fiecare minut $i$ ($1 ≤ i ≤ n$) el vorbește despre subiectul $s[~i~]$.
Numim *delir* o subsecvență *maximală* de minute în care Călin vorbește despre același subiect. Numim *delir de gravitate $k$* un delir cu durata de $k$ minute.
Dorim să răspundem la $q$ interogări definite prin triplete $l$, $r$, $k$ cu semnificația: Dacă luăm în calcul doar intervalul de la minutul $l$ pînă la minutul $r$ inclusiv, cîte deliruri de gravitate *cel puțin* $k$ există?
Poveste și cerință...
h2. Date de intrare
Fișierul de intrare $calin.in$ conține pe prima linie numerele $n$ și $q$, separate prin spațiu. A doua linie conține valorile $s[~1~] s[~2~] ... s[~n~]$, separate prin spații. Fiecare dintre următoarele $q$ linii conține cîte un triplet de numere $l r k$ cu semnificația de mai sus.
Fișierul de intrare $calin.in$ ...
h2. Date de ieșire
În fișierul de ieșire $calin.out$ afișați răspunsurile la interogări, cîte unul pe linie, în aceeași ordine ca la intrare.
În fișierul de ieșire $calin.out$ ...
h2. Restricții
* $1 ≤ n, q ≤ 200.000$
* $1 ≤ s[~i~] ≤ 9$ pentru orice $1 ≤ i ≤ n$
* $1 ≤ l ≤ r ≤ n$ și $1 ≤ k ≤ r − l + 1$ pentru fiecare interogare
table{width: inherit}.
|_. subtask |_. puncte |_. restricții |
| 1 | 15 | $n, q ≤ 15.000$ |
| 2 | 55 | $n, q ≤ 80.000$ |
| 3 | 30 | Fără restricții suplimentare. |
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
table(example).
|_. calin.in |_. calin.out |
| 8 5
6 4 4 4 1 1 1 4
2 6 2
3 6 2
3 6 3
3 8 3
3 8 1
| 2
2
0
1
3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicații
h3. Explicație
* Interogarea 1: Pe subsecvența (4 4 4 1 1) există un delir de gravitate 3 și un delir de gravitate 2. Așadar, există două deliruri de gravitate *cel puțin* 2.
* Interogările 2-3: Pe subsecvența (4 4 1 1) există două deliruri de gravitate 2. Subliniem că aceste deliruri *nu* au gravitate 3, căci considerăm doar pozițiile 3-6.
* Interogările 4-5: Pe subsecvența (4 4 1 1 1 4) există un delir de gravitate 1, un delir de gravitate 2 și un delir de gravitate 3.
...
== include(page="template/taskfooter" task_id="calin") ==
