Paréntesis dinámicos
Los habitantes de IslaGrande consideran que una cadena de paréntesis está balanceada si la cadena está vacía, si o si , donde y 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: , la longitud de la cadena de paréntesis.
- Linea 2: , una cadena de paréntesis de longitud . El primer carácter de la cadena está en la posición 1 y el último en la posición .
- Linea 3: , 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 de la cadena .
u a b invierte todos los paréntesis en el intervalo de la cadena .
La secuencia de caracteres en el intervalo consiste de los todos los caracteres en las posiciones entre la y la incluyendo ambos.
Salida
La salida contiene para cada solicitud de tipo (del primer tipo definido), una línea con un entero: si la cadena está balanceada y si la cadena no lo está.
Restricciones
- .
- En el 20% de los casos de prueba, .
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
This comment is hidden due to too much negative feedback. Show it anyway.