== include(page="template/taskheader" task_id="marbles") ==
Poveste si cerinta...
Gigel are {$N$} bilute colorate pe care le aseaza pe axa {$Ox$} a unui sistem cartezian de coordonate. Gigel efectueaza urmatoarele operatii:
* {$0 i j$} va reprezenta o operatie de mutare a bilei aflata la coordonata {$i$} la coordonata {$i+j$}. O restrictie asupra acestei operatii este faptul ca in urma ei ordinea initiala a bilelor nu se va modifica.
* {$1 i j$} Gigel se intreaba care este numarul maxim de bile de aceeasi culoare care se afla in intervalul [{$i,j$}].
h2. Cerinta
Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatie de tip {$1$}.
h2. Date de intrare
Fisierul de intrare $marbles.in$ ...
Fisierul de intrare $marbles.in$ contine pe prima linie numerele {$N$} si {$M$}, numarul de bilute, respectiv de operatii. Pe urmatoarele {$N$} linii se afla cate doua numere intregi {$a{~i~} b{~i~}$} reprezentand coordonata la care se afla initial bila {$i$}, respectiv culoarea ei. Urmeaza apoi {$M$} linii fiecare descriind o operatie facuta de Gigel.
h2. Date de iesire
In fisierul de iesire $marbles.out$ ...
In fisierul de iesire $marbles.out$ va contine pentru fiecare operatie de tipul {$1$} din input, raspunsul corespunzator.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* Culoarea unei bile va fi un numar natural din intervalul [{$1,64$}]
*
h2. Exemplu
table(example). |_. marbles.in |_. marbles.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3
1 1
4 1
5 2
11 1
15 3
1 4 13
0 4 -1
1 4 13
| 2
1
|
h3. Explicatie
...
In intervalul [{$4,13$}] initial se afla doua bile de tip {$1$}.
Dupa mutarea bilei de pe pozitia {$4$} pe pozitia {$4-1=3$} in intervalul [{$4,13$}] mai ramane doar o bila de tip {$1$} si una de tip {$2$}.
== include(page="template/taskfooter" task_id="marbles") ==
