De aceasta problema s-a lovit autorul cand a implementat un engine de Worms.
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.
Vom imparti sirul in bucati de lungime fixa
Solutiile in
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.
