https://www.geeksforgeeks.org/range-queries-longest-correct-bracket-subsequence/
Range Queries for Longest Correct Bracket Subsequence
struct DATA{
int open_brackets;
int close_brackets;
DATA(){
open_brackets=close_brackets = 0;
}
};
DATA sum[4*MAX];
char str[MAX];
void build_tree(int node, int a, int b){
if(a>b){
return;
}
if(a==b){
if(str[a]=='('){
sum[node].open_brackets = 1;
sum[node].close_brackets = 0;
}
else{
sum[node].open_brackets = 0;
sum[node].close_brackets = 1;
}
// cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
return;
}
build_tree(2*node, a, (a+b)/2);
build_tree((2*node)+1,((a+b)/2)+1, b);
int ol = sum[2*node].open_brackets;
int cl = sum[2*node].close_brackets;
int orr = sum[2*node+1].open_brackets;
int crr = sum[2*node+1].close_brackets;
if(ol>=crr){
sum[node].open_brackets = ol + orr - crr;
}
else {
sum[node].open_brackets = orr;
}
if(ol<=crr){
sum[node].close_brackets = cl+crr-ol;
}
else{
sum[node].close_brackets = cl;
}
// cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
}
void update_tree(int node, int a, int b, int val){
if(a>b){
return;
}
if(a==b){
if(str[val]=='('){
sum[node].open_brackets--;
sum[node].close_brackets++;
str[val] = ')';
}
else{
sum[node].open_brackets++;
sum[node].close_brackets--;
str[val] = '(';
}
//cout<<str<<endl;
return;
}
if(val <=(a+b)/2){
update_tree(2*node, a, (a+b)/2,val);
}
else{
update_tree((2*node)+1,((a+b)/2)+1, b,val);
}
int ol = sum[2*node].open_brackets;
int cl = sum[2*node].close_brackets;
int orr = sum[2*node+1].open_brackets;
int crr = sum[2*node+1].close_brackets;
if(ol>=crr){
sum[node].open_brackets = ol + orr - crr;
}
else {
sum[node].open_brackets = orr;
}
if(ol<=crr){
sum[node].close_brackets = cl+crr-ol;
}
else{
sum[node].close_brackets = cl;
}
}
Range Queries for Longest Correct Bracket Subsequence
Given a bracket sequence or in other words a string S of length n, consisting of characters ‘(‘ and ‘)’. Find length of the maximum correct bracket subsequence of sequence for a given query range. Note: A correct bracket sequence is the one that have matched bracket pairs or which contains another nested correct bracket sequence. For e.g (), (()), ()() are some correct bracket sequence.
Examples:
Input : S = ())(())(())( Start Index of Range = 0, End Index of Range = 11 Output : 10 Explanation: Longest Correct Bracket Subsequence is ()(())(()) Input : S = ())(())(())( Start Index of Range = 1, End Index of Range = 2 Output : 0
Segment Trees can be used to solve this problem efficiently
At each node of the segment tree, we store the following:
1) a - Number of correctly matched pairs of brackets. 2) b - Number of unused open brackets. 3) c - Number of unused closed brackets.
(unused open bracket – means they can’t be matched with any closing bracket, unused closed bracket – means they can’t be matched with any opening bracket, for e.g S = )( contains an unused open and an unused closed bracket)
For each interval [L, R], we can match X number of unused open brackets ‘(‘ in interval [L, MID] with unused closed brackets ‘)’ in interval [MID + 1, R] where
X = minimum(number of unused ‘(‘ in [L, MID], number of unused ‘)’ in [MID + 1, R])
Hence, X is also the number of correctly matched pairs built by combination.
So, for interval [L, R]
X = minimum(number of unused ‘(‘ in [L, MID], number of unused ‘)’ in [MID + 1, R])
Hence, X is also the number of correctly matched pairs built by combination.
So, for interval [L, R]
1) Total number of correctly matched pairs becomes the sum of correctly matched pairs in left child and correctly matched pairs in right child and number of combinations of unused ‘(‘ and unused ‘)’ from left and right child respectively.
a[L, R] = a[L, MID] + a[MID + 1, R] + X
2) Total number of unused open brackets becomes the sum of unused open brackets in left child and unused open brackets in right child minus X (minus – because we used X unused ‘(‘ from left child to match with unused ‘) from right child).
a[L, R] = b[L, MID] + b[MID + 1, R] - X
3) Similarly, for ununsed closed brackets, following relation holds.
a[L, R] = c[L, MID] + c[MID + 1, R] - X
where a, b and c are the representations described above for each node to be stored in.
https://www.geeksforgeeks.org/range-queries-longest-correct-bracket-subsequence-set-2/
https://www.spoj.com/problems/BRCKTS/
Idea is based on the Post length of the longest valid balanced substring If we marked indexes of all Balanced parentheses/bracket in a temporary array (here we named it BCP[], BOP[] ) then we answer each query in O(1) time.
Algorithm :
Algorithm :
stack is used to get the index of blanace Breacket Travese a string from 0 ..to n IF we seen a closing bracket, ( i.e., str[i] = ')' && stack is not empty ) Then mark both "open & close" bracket indexs as 1 . BCP[i] = 1; BOP[stk.top()] = 1; And At lest stored cumulative sum of BCP[] & BOP[] Run a loop from 1 to n BOP[i] +=BOP[i-1], BCP[i] +=BCP[i-1]
Now you can answer each query in O(1) time
(BCP[e] - (BOP[s-1] - BCP[s-1] ) )*2;
https://www.spoj.com/problems/BRCKTS/
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 i-th 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 k-th 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 i-th 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.)
Test i:
where i is replaced by the number of the test and in the following lines, for every check operation in the i-th 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]http://codechrist.blogspot.com/2015/01/spoj-61-brackets-solution.html
struct DATA{
int open_brackets;
int close_brackets;
DATA(){
open_brackets=close_brackets = 0;
}
};
DATA sum[4*MAX];
char str[MAX];
void build_tree(int node, int a, int b){
if(a>b){
return;
}
if(a==b){
if(str[a]=='('){
sum[node].open_brackets = 1;
sum[node].close_brackets = 0;
}
else{
sum[node].open_brackets = 0;
sum[node].close_brackets = 1;
}
// cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
return;
}
build_tree(2*node, a, (a+b)/2);
build_tree((2*node)+1,((a+b)/2)+1, b);
int ol = sum[2*node].open_brackets;
int cl = sum[2*node].close_brackets;
int orr = sum[2*node+1].open_brackets;
int crr = sum[2*node+1].close_brackets;
if(ol>=crr){
sum[node].open_brackets = ol + orr - crr;
}
else {
sum[node].open_brackets = orr;
}
if(ol<=crr){
sum[node].close_brackets = cl+crr-ol;
}
else{
sum[node].close_brackets = cl;
}
// cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
}
void update_tree(int node, int a, int b, int val){
if(a>b){
return;
}
if(a==b){
if(str[val]=='('){
sum[node].open_brackets--;
sum[node].close_brackets++;
str[val] = ')';
}
else{
sum[node].open_brackets++;
sum[node].close_brackets--;
str[val] = '(';
}
//cout<<str<<endl;
return;
}
if(val <=(a+b)/2){
update_tree(2*node, a, (a+b)/2,val);
}
else{
update_tree((2*node)+1,((a+b)/2)+1, b,val);
}
int ol = sum[2*node].open_brackets;
int cl = sum[2*node].close_brackets;
int orr = sum[2*node+1].open_brackets;
int crr = sum[2*node+1].close_brackets;
if(ol>=crr){
sum[node].open_brackets = ol + orr - crr;
}
else {
sum[node].open_brackets = orr;
}
if(ol<=crr){
sum[node].close_brackets = cl+crr-ol;
}
else{
sum[node].close_brackets = cl;
}
}
The third problem: BRCKTS, we’ll look at is very different from the first two but the differences are only superficial since we’ll be able to solve it using the same structure. This problem gives a string containing parenthesis (open and closed), requires making updates to individual parenthesis (changing an open parenthesis to closed or vice versa), and checking if the whole string represents a correct parenthesization.
As it turns out, we need only 2 things in each segment tree node:
As it turns out, we need only 2 things in each segment tree node:
- The number of unmatched open parenthesis in this range
- The number of unmatched closed parenthesis in this range