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

'Editorialul':problema/brperm/editorial
 

h2. SE DA UN ARBORE...

Consideram permutare $BR$: bit reverse.
Un sir de lungime $2^k$ este $BR-permutare$ daca si numai daca este egal cu el insusi dupa ce se aplica $BR$.
Se da un sir de caractere de lungime $N$, indexat de la 0. Sirul de caractere $S(i, j)$ este sirul de caractere de lungime $2^j^$ ce incepe pe pozitia $i$, daca el exista. Functia $brperm(i, j)$ este $1$ daca $S(i, j)$ exista si este $BR-permutare$, iar 0 altfel. In aceasta problema se cere sa calculati eficient functia $brperm$.

Notă: În enunţ, b1...bk reprezintă un întreg scris în notaţie binară, unde b1 este cel mai semnificativ bit, iar bk este cel mai puţin semnificativ bit.
Vrăjitoarea Roxana, în timp ce zbura pe mătură prin galaxie, a descoperit o nouă planetă (paneta BR-PERM) unde toţi locuitorii erau implicaţi într-un dans ciudat. În acest dans, participanţii stau într-o linie, iar apoi se reordonează. Într-un dans la care participa 2k locuitori, persoana de pe poziţia  b1...bk se va muta la poziţia bk...b1 (indexat de la 0).
Roxana a realizat că fiecare persoana de pe BR-PERM poartă îmbrăcaminte din una dintre cele 26 de culori. Aceste culori vor fi reprezentate de litere din alfabetul Latin.
BR-PERM-ienii consideră speciale şirurile de dansatori unde secvenţa de culori pe care locuitorii le poarta înainte şi după dans sunt la fel. Ei numesc astfel de secvenţe drăguţe. De exemplu, cand k=2, avem un şir de 4 dansatori 0, 1, 2, 3 care dupa dans va fi ordonat în următorul fel: 0, 2, 1, 3. Astfel secvenţa de culori abbaeste drăguţă, dar abca nu este.
BR-PERM-ienii o roagă pe Roxana să îi ajute cu această problemă (se pare că vrăjitoarele mereu ajută oamenii să îşi rezolve problemele. Aceştia îi arată un şir de n dansatori şi o roagă să îi răspundă la mai multe întrebari: "Este secvenţa de lungime 2k care începe la dansatorul i drăguţă?

Se vrea problema cu manager la RMI. Acolo vom da cu "implementati $void init(string s);$ si $bool brperm(int, int)$.

h2. Date de intrare

h2. Restricţii

* *SIGMA = 26*

* $1 ≤ N ≤ 500000$
 
* $1 ≤ Q ≤ 500000$

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

h2. Punctare

* 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

h3. Subtask 1 (

h2. Exemplu