The students of UBB Cluj have a lot of free time, and so does Comisia.
After returning to Cluj-Napoca from Bucharest and finishing her introspective analysis of the city's infrastructure, she decided to make a game. She doesn't want to create a very complex game (after all, she wants to finish it today), so she chose to clone the standard game of Worms. To make things easier for her, she will only implement a 1D version of it (because switching to 2D (or even 3D) is easy after finishing the 1D version).
A few hours have passed since she started writing the code and almost all of the graphics functions are ready. The main structure of the game is also finished. However an important problem arose and, after thinking about it for more than half an hour, she asks you for help.
You are given a 1-based indexed array of length N denoted by v, whose elements are 0 or 1, all of them being initially set to 0. You must execute M operations on this array:
- 1 a b c
- Set
v[a], v[a+1], ..., v[b]toc - 2 a
- Print 3 numbers,
v[a], y, zwhere y is the smallest index such thatv[y], v[y+1], ..., v[a]are equal and z is the largest index such thatv[a], v[a+1], ..., v[z]are equal.
Help Comisia by writing a program which solves this problem and she will be able to finish her game in no time.
Input
On the first line of the input there areN and M. Each of the next M lines contains the description of a query. Output
Print the answer to each operation of type 2, as described above.Constraints
1 ≤ N, M ≤ 50000For every query,
1 ≤ a ≤ b ≤ n and c is 0 or 1. Sample
| Input | Output |
|---|---|
| 7 10 2 3 1 2 3 1 2 3 1 3 4 0 2 3 1 3 6 1 2 5 2 1 1 3 5 0 2 4 | 0 1 7 1 2 3 0 3 7 1 2 6 0 1 1 0 3 5 |
O(N*M)
Se realizeaza operatiile de query si update exact cum sunt ele prezentate in enunt, element cu element. Aceasta solutie este prea inceata pentru a trece de testele oficiale, desi a pacalit multa lume, trecand cu succes de preteste. O(NsqrtN)
Vom imparti sirul in bucati de lungime fixa SQ = sqrtN, tinand minte pentru fiecare bucata all[piece] - daca elementele din bucata piece au toate aceeasi valoare si vl[piece] - ce valoare au elementele din acea bucata. Acum la fiecare update daca bucata pe care o consideram este inclusa complet in intervalul curent, vom actualiza all si vl. Insa daca intervalul se intersecteaza cu partea pe care facem update vom lucra cu sirul initial actualizand fiecare element din acesta facand maxim SQ calcule. Aceasta solutie este in opinia unui membru al comisiei bucati de sqrt cu lazy update. O(Nlog2N) si O(NlogN)
Solutiile in O(Nlog2N) si O(NlogN) raman tema cititorului, acestea fiind asemanatoare cu multe probleme propuse la diverse concursuri de informatica. Implementarea acestor solutii era mult mai dificila decat solutia de mai sus, nefiind necesare pentru incadrarea in timp. Solutie bonus
In loc sa retinem tot sirul vom retine in nodurile unei liste simplu inlantuite doar capetele intervalelor umplute cu 0 sau 1 si valoarea din interval. Se observa ca nu e necesar sa retinem nodurile sub forma de interval ci putem sparge intervalula, b in 2 noduri a, b+1. In fiecare nod vom retine valoarea din sir care incepe pe pozitia din nod si se continua pana la pozitia urmatorului nod. De exemplu, pentru sirul: 0 0 1 0, vom avea nodurile (1,0), (3,1), (4,0). La fiecare update vom sparge niste intervale actualizand corespunzator nodurile din lista. Pentru aceasta avem nevoie de cel mai apropiat nod din stanga si din dreapta nodurilor a si b. Pentru aceasta putem folosi un skip list si sa obtinem complexitatea O(NlogN). Aceasta solutie e utila cand nu stim dimensiunea sirului si cand putem avea multe operatii.
