Fişierul intrare/ieşire:luffpar.in, luffpar.outSursăInfoOltenia 2018 - Clasele 11 - 12
AutorMihai PopaAdăugată deinfoolteniaInfo-Oltenia 2018 infooltenia
Timp execuţie pe test2.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Luffpar

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:

  1. 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 ‘(‘
  2. 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.

Date de intrare

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.

Date de ieşire

Î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.

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

Exemplu

luffpar.inluffpar.out
5
()(()
5
2 1 2
1 4 5
2 3 4
2 1 4
2 4 5
1
1
1
0

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?