== include(page="template/taskheader" task_id="luffpar") ==
Poveste şi cerinţă...
Bluff a descoperit recent în maşina gri o secvenţă de paranteze rotunde. Din motive necunoscute, el doreşte să efectueze următoarele operaţii pe baza noii descoperiri:
# operaţie de tipul $1$: dându-se $l$ si $r$ două poziţii valide ale secvenţei, să se modifice toate parantezele dintre $l$ si $r$ inclusiv - astfel, parantezele ‘(‘ devin ‘)’ iar cele ‘)’ devin ‘(‘
# operaţie de tipul $2$: dându-se $l$ si $r$ două poziţii valide ale secvenţei, să se spună daca subsecvenţa de paranteze dintre $l$ si $r$ reprezintă sau nu o parantezare corecta. Formal, o parantezare corectă este construită conform următoarelor reguli:
** <parantezare corectă> = <secvenţă vida>
** <parantezare corectă> = “(“ + <parantezare corectă> + “)”
** <parantezare corectă> = <parantezare corectă> + <parantezare corectă>
Următoarele reprezintă exemple de parantezari corecte: (), (()()), (()())(), (()())(()())
Următoarele reprezintă exemple de parantezari incorecte: )), )(, ()), ())(, (()))(
Dându-se secvenţa iniţială de paranteze, precum si operaţiile pe care Bluff vrea să le efectueze, ajutaţi-l să raspundă la operaţiile de tip $2$.
h2. Date de intrare
Fişierul de intrare $luffpar.in$ ...
Prima linie a fişierului $luffpar.in$ va conţine numărul $n$, reprezentând lungimea secvenţei de paranteze.
A doua line va conţine exact $n$ caractere, reprezentând secvenţa de paranteze. Caracterele vor fi doar paranteze rotunde: ( sau ).
A treia linie va conţine numărul $m$ reprezentând numărul de operaţii pe care Bluff vrea să le efectueze.
Pe următoarele $m$ linii se vor găsi câte trei numere întregi: $tip l r$, care descriu fiecare operaţie ce trebuie aplicată. $tip$ poate fi $1$ sau $2$, identificând tipul de operaţie care trebuie aplicată. $l$ si $r$ descriu subsecvenţa pe care trebuie aplicată operaţia, iar poziţiile secvenţei sunt numerotate de la $1$. Se garantează că, pentru orice operaţie, $1 ≤ l ≤ r ≤ n$.
h2. Date de ieşire
În fişierul de ieşire $luffpar.out$ ...
În fişierul $luffpar.out$ afişaţi răspunsurile corespunzătoare operaţiilor de tip $2$. Un răspuns poate fi $1$, în cazul unei secvenţe corect parantezate, sau $0$ alftel.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 200.000$
* $1 ≤ m ≤ 200.000$
* pentru $20%$ dintre teste: $n, m ≤ 1000$
* pentru alte $30%$ dintre teste se garantează ca fiecare operaţie de tipul $1$ se va aplica asupra unei subsecvenţe de lungime exact $1$, deci $l = r$ va fi adevarat pentru toate operaţiile de tipul $1$
h2. Exemplu
table(example). |_. luffpar.in |_. luffpar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
()(()
5
2 1 2
1 4 5
2 3 4
2 1 4
2 4 5
| 1
1
1
0
|
h3. Explicaţie
...
Subsecvenţa corespunzătoare primei operaţii este (), care este o parantezare corectă, deci se afişează $1$.
După a doua operaţie, secvenţa devine: ()()(
Subsecvenţa corespunzătoare următoarei operaţii este acum (), care este o parantezare corecta.
Subsecvenţa corespunzătoare următoarei operaţii este acum ()(), care este o parantezare corecta.
Subsecvenţa corespunzătoare următoarei operaţii este )(, care nu este o parantezare corecta, deci se afişează $0$.
== include(page="template/taskfooter" task_id="luffpar") ==
== include(page="template/taskfooter" task_id="luffpar") ==
