vikalp14's blog

By vikalp14, 4 months ago, ,

For each node (for example x), we keep three integers : 1.t[x] = Answer for it's interval. 2. o[x] = The number of

Unable to parse markup [type=CF_MATHJAX]

)\$s after deleting the brackets who belong to the correct bracket sequence in this interval whit length t[x].

So, as you know, first of all we need a build function which would be this : (as above) (C++ and [l, r) is inclusive-outclusive )

void build(int id = 1,int l = 0,int r = n){
if(r - l < 2){
if(s[l] == '(')
o[id] = 1;
else
c[id] = 1;
return ;
}
int mid = (l+r)/2;
build(2 * id,l,mid);
build(2 * id + 1,mid,r);
int tmp = min(o[2 * id],c[2 * id + 1]);
t[id] = t[2 * id] + t[2 * id + 1] + tmp;
o[id] = o[2 * id] + o[2 * id + 1] - tmp;
c[id] = c[2 * id] + c[2 * id + 1] - tmp;
}


For queries, return value of the function should be 3 values : t, o, c which is the values I said above for the intersection of the node's interval and the query's interval (we consider query's interval is [x, y) ), so in C++ code, return value is a pair<int,pair<int,int> > (pair<t, pair<o,c> >) :

typedef pair<int,int>pii;
typedef pair<int,pii>   node;
node segment(int x,int y,int id = 1,int l = 0,int r = n){
if(l >= y || x >= r)   return node(0,pii(0,0));
if(x <= l && r <= y)
return node(t[id],pii(o[id],c[id]));
int mid = (l+r)/2;
node a = segment(x,y,2 * id,l,mid), b = segment(x,y,2 * id + 1,mid,r);
int T, temp, O, C;
temp = min(a.y.x , b.y.y); //why
T = a.x + b.x + temp;      //repeat
O = a.y.x + b.y.x - temp;  //these steps
C = a.y.y + b.y.y - temp; //wasnt it alreasy performed while building the segment
return node(T,pii(O,C));
}


why are the last steps of both functions repeating, T,O,C was already updated during build, if it is updated again during segment then it should be wrong?

• 0