== include(page="template/taskheader" task_id="brperm") ==

'Editorialul':problema/brperm/editorial
 
h2. SE DA UN ARBORE...
 

Poveste şi cerinţă...

Am considerat ca sunt date anumite queryuri in input, daca secventa cutare e sau nu br-palindrom. Desigur, putem schimba formatul asta in varianta originala, in caz ca devine inutila schimbarea.
 
 
*Queryurile sunt doar pe lantul catre radacina* - nu vrem lca-uri si alte nebunii
 

h2. Date de intrare
Fişierul de intrare $brperm.in$ ...
h2. Date de ieşire

În fişierul de ieşire $brperm.out$ ...

În fişierul de ieşire $brperm.out$ *se afla un sir binar...*

h2. Restricţii

* *SIGMA = 26*
 

* $... ≤ ... ≤ ...$

* Subtask1 (10 puncte): O(Q * N * logN) && *NU* neaparat linie
* Subtask2 (10 puncte): O(N * logN + Q * N) && *NU* neaparat linie
* Subtask3 (10 puncte): O(N * logN + Q) && linie && SIGMA = 2 && biased random (comisia a ales, pt fiecare test, cate un numar real $p$ intre $0$ si $1$ iar fiecare caracter este 'a' cu probabilitate $p$ si 'b' cu probabilitate $1-p$)
* Subtask4 (30 puncte): O((N + Q) * logN * logN) sau O((N + Q) * sqrt(N + Q) + Q) (nu cunosc solutie, dar cine stie?) - anulat si inghitit de subtaskul urmator in caz ca nu dam queryuri
* Subtask5 (10 puncte): O(N * logN * logN + Q) - acelasi lucru ca subtaskul urmator daca nu dam queryuri
* Subtask6 (10 puncte): O((N + Q) * logN) - in caz ca exista
* Subtask7 (20 puncte): O(N * logN + Q) - in caz ca exista, altfel punctele merg la ultimul subtask existent
 

h2. Exemplu
table(example). |_. brperm.in |_. brperm.out |