vikalp14's blog

By vikalp14, 5 years ago, In English

contest https://codeforces.com/contest/380/problem/C Algorithm gym https://codeforces.com/blog/entry/15890

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it