BRCKTS  Brackets
We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that
 every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
 for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets
 replacement  changes the ith bracket into the opposite one
 check  if the word is a correct bracket expression
Task
Write a program which
 reads (from standard input) the bracket word and the sequence of operations performed,
 for every check operation determines if the current bracket word is a correct bracket expression,
 writes out the outcome (to standard output).
Input
Ten test cases (given one under another, you have to process all!). Each of the test cases is a series of lines. The first line of a test consists of a single number n (1<=n<=30000) denoting the length of the bracket word. The second line consists of n brackets, not separated by any spaces. The third line consists of a single number m  the number of operations. Each of the following m lines carries a number k denoting the operation performed. k=0 denotes the check operation, k>0 denotes replacement of kth bracket by the opposite.
Output
For every test case your program should print a line:
Test i:
where i is replaced by the number of the test
and in the following lines, for every check operation in the ith test
your program should print a line with the word
YES,
if the current bracket word is a correct bracket expression, and a line
with a word
NO otherwise.
(There should be as many lines as check operations in the test.)
Example
Input: 4 ()(( 4 4 0 2 0 [and 9 test cases more] Output: Test 1: YES NO [and 9 test cases more]Warning: large Input/Output data, be careful with certain languages
hide comments
ankitjosh:
20240512 23:08:15
might seem like the trivial idea doesn't work but it does work! 

yogman:
20230619 14:39:36
Very good question 

rapiram31:
20221128 22:43:07
Maybe get the segment tree values as prefix sum values, then its easy for you guys to find the minimum prefix, just when updating add the values directly to minimum so minimum won't change


t0nhou:
20220506 22:07:43
What's the m limit?


Christoph Dürr:
20211029 01:06:54
Time limit seems to be too strict for Python 

yasser1110:
20210727 12:49:39
@abid1729 No. See https://en.wikipedia.org/wiki/Contextfree_grammar#Wellformed_parentheses 

yasser1110:
20210727 12:48:50
This was straightforward problem if you can figure out how to merge left and right halves of the string and figure out if its valid or not.


sicho_mohit:
20210709 20:20:26
I have tried each and everything , still my code is giving TLE.


wheneveright:
20210527 05:05:07
@lokesh_2052 I think you should find the min sum in the segment tree. For example ))(( is 1 1 1 1, and it's sumsegment tree is based on 1 2 1 0, then find min in the segment tree.


lokesh_2052:
20210214 16:30:58
I did this in 2.42s. I could not do myself . I find confusion ))(( is right or wrong . this is wrong!!!!!!

Added by:  Adam Dzedzej 
Date:  20040615 
Time limit:  11s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  Internet Contest Pogromcy Algorytmow(Algorithm Tamers) 2003 Round IV 