== 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. Asupra acestora el efectueaza urmatoarele operatii:
* {$0 i j$} va reprezenta o operatie de mutare a bilei aflata la coordonata {$i$} la coordonata {$i+j$}. Se garanteaza faptul ca intre coordonatele $i$ si $i+j$ nu exista nicio alta bila.
* {$1 i j$} reprezinta operatia de interogare. Astfel, Gigel se intreaba care este numarul maxim de bile de aceeasi culoare care se afla intre coordonatele $i$ si {$j$} inclusiv.
h2. Cerinta
Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatiile de interogare.
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 numarul de operatii efectuate. 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$ ...
Fisierul de iesire $marbles.out$ va contine pentru fiecare operatie de interogare raspunsul corespunzator.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
* Culoarea unei bile va fi un numar natural din intervalul [{$1, 64$}]
* Coordonatele bilelor la orice moment de timp, precum si toate numerele din fisierul de intrare, vor fi intregi cu semn ce se vor incadra pe {$32$} de biti.
* Nu vor exista $2$ bile la aceeasi coordonata
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
...
Initial, intre coordonatele $4$ si $13$ exista doua bile care sunt colorate cu $1$. Dupa mutarea bilei de pe pozitia {$4$} pe pozitia {$4$} - {$1$} = {$3$}, intre coordonatele $4$ si $13$ mai raman doar doua bile, ambele fiind colorate diferit.
== include(page="template/taskfooter" task_id="marbles") ==
