Paréntesis dinámicos


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Los habitantes de IslaGrande consideran que una cadena W de paréntesis está balanceada si la cadena está vacía, si W=(W_1) o si W=W_1W_2, donde W_1 y W_2 están balanceadas. Por ejemplo, las cadenas \(“(())”, “()()”, “(()())”\) están balanceadas y las cadenas \(“)”, “))((”, “(()(()”\) no lo están. Ellos necesitan construir un programa que actualice dinámicamente una cadena de paréntesis de acuerdo a dos tipos de solicitudes: el primero averigua si una secuencia de la cadena en un intervalo está balanceada o no mientras que el segundo tipo de solicitud cambia los paréntesis cerrados por abiertos y viceversa en un determinado intervalo de la cadena de paréntesis.

Tarea

Hacer un programa que permita:

  • Leer desde la entrada la longitud y cadena de paréntesis así como la cantidad de solicitudes y las solicitudes propiamente.
  • Ejecutar cada solicitud.
  • Escribir hacia la salida para cada solicitud del primer tipo, un uno si la secuencia de la cadena está balanceada o un cero en caso contrario.

Entrada

La entrada contiene en la:

  • Linea 1: N, la longitud de la cadena de paréntesis.
  • Linea 2: W, una cadena de paréntesis de longitud N. El primer carácter de la cadena está en la posición 1 y el último en la posición N.
  • Linea 3: S, el número de solicitudes.
  • Linea 4..S+4: cada una de estas líneas contiene una solicitud, en uno de los formatos siguientes:

    q a b devuelve si la secuencia está o no balanceada en el intervalo [a,b] de la cadena W.

    u a b invierte todos los paréntesis en el intervalo [a,b] de la cadena W.

La secuencia de caracteres en el intervalo [a,b] consiste de los todos los caracteres en las posiciones entre la a y la b incluyendo ambos.

Salida

La salida contiene para cada solicitud de tipo q (del primer tipo definido), una línea con un entero: 1 si la cadena está balanceada y 0 si la cadena no lo está.

Restricciones

  • 1 \leq N, S \leq 200 000.
  • En el 20% de los casos de prueba, N, S \leq 50 000.

Ejemplo de Entrada

6
((()))
8
q 1 6
q 2 6
u 3 4
q 2 3
q 4 5
u 1 2
q 4 5
q 1 6

Ejemplo de Salida

1
0
1
1
1
0

Comments


  • -7
    Primervirgen  commented on Dec. 21, 2019, 6:52 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.