Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | kinder.in, kinder.out | Sursă | Lot 2008 - Piatra Neamt, Baraj2 |
| Autor | Andrei Grigorean | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kinder
Bunicuta Miruna are N nepotei care sunt asezati in linie si sunt numerotati de la stanga spre dreapta, in ordine, cu numere naturale distincte de la 1 la N. Deoarece se apropie Ziua Copilului, Miruna le-a cumparat nepoteilor mai multe oua Kinder. Aceste oua Kinder nu sunt toate la fel, ci sunt de M tipuri (numerotate de la 1 la M) si doua culori ( 0 - rosu si 1 - albastru). Tipul oului precizeaza cat de gustos este oul (daca tipul t1<t2, atunci un ou de tipul t1 va fi mai gustos decat un ou de tipul t2). Miruna va efectua operatii de urmatoarele 3 tipuri:
| Tip | Nume | Format | Efect |
|---|---|---|---|
| 1 | Update | c t p q | Copilul c primeste q oua de tip t si culoare p |
| 2 | Update | c t | Copilul c ia fiecare ou de tipul t care este al sau si il vopseste in culoarea opusa (din 0 in 1 si din 1 in 0) |
| 3 | Query | a b p x | Miruna se uita la ouale de culoare p care apartin copiilor din intervalul [a, b] si vrea sa afle tipul celui de-al x-lea cel mai gustos ou. |
Scrieti un program care sa efectueze in mod eficient toate operatiile descrise.
Date de intrare
Fisierul de intrare kinder.in va contine pe prima linie 3 numere naturale N M T, reprezentand numarul de nepotei, numarul de tipuri de oua, respectiv numarul de operatii ce vor fi efectuate. Pe fiecare dintre urmatoarele T linii va fi descrisa cate o operatie. Linia care descrie o operatie incepe cu un numar ($1$, 2 sau 3) care indica tipul operatiei, urmat de 4, 2, respectiv 4 numere naturale conform formatului operatiei. Valorile scrise pe aceeasi linie sunt separate prin spatiu.
Date de iesire
Fisierul de iesire kinder.out va contine cate o linie pentru fiecare operatie de tip 3 efectuata. Pe linia i se afla raspunsul pentru cea de a i-a operatie de tip 3 din fisierul de intrare.
Restrictii
- 1 ≤ N, M, T ≤ 50000
- Pentru operatii de tipul 1: 1 ≤ c ≤ N, 1 ≤ t ≤ M, 0 ≤ p ≤ 1, 1 ≤ q ≤ 1000
Pentru operatii de tipul 2: 1 ≤ c ≤ N, 1 ≤ t ≤ M
Se garantează că nepotul c are cel puţin un ou de tip t
Pentru operaţii de tipul 3: 1 ≤ a ≤ b ≤ N, 0 ≤ p ≤ 1
1 ≤ x ≤ Numărul total de ouă de culoare p pe care le deţin nepoţii din intervalul [a, b]
Se garantează că nepoţii din intervalul [a,b] deţin cel puţin un ou de culoare p.
Exemplu
| kinder.in | kinder.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
