Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const long long MX = (1<<19);
  4. struct node{
  5.     int open , close , ans;
  6.     node(){
  7.         open = close = ans = 0;
  8.     }
  9.     node(int open , int close , int ans):open(open) , close(close) , ans(ans){}
  10. }tree[MX*4];
  11. string str;
  12. int idx[MX];
  13. node merge_(node L , node R){
  14.     node ret = node(L.open + R.open , L.close + R.close , L.ans + R.ans);
  15.     int add = min(L.open , R.close);
  16.     ret.open -= add;
  17.     ret.close -= add;
  18.     ret.ans  += add;
  19.     return ret;
  20. }
  21. void build(int x , int a , int b){
  22.     if(a == b){
  23.         idx[a] = x;
  24.         if(str[a] == '(')
  25.             tree[x] = node(1 , 0 , 0);
  26.         else tree[x] = node(0 , 1 , 0);
  27.         return;
  28.     }
  29.     build(x*2 , a , (a+b)/2);
  30.     build(x*2+1 , (a+b)/2+1 ,b);
  31.     tree[x] = merge_(tree[x*2] , tree[x*2+1]);
  32. }
  33. void nk7(int x){
  34.     x = idx[x]; tree[x] = node();
  35.     x >>= 1;
  36.     while(x > 0){
  37.         tree[x] = merge_(tree[x*2] , tree[x*2+1]);
  38.         x >>= 1;
  39.     }
  40. }
  41. int st , en;
  42. node query(int x , int a , int b){
  43.     if(st > b || en < a) return node();
  44.     if(a >= st && b <= en) return tree[x];
  45.     return merge_(query(x*2 , a ,(a+b)/2) , query(x*2+1 , (a+b)/2+1 , b));
  46. }
  47. char ccc[MX];
  48. int n;
  49. set < int > open , close , all;
  50. vector < int > ans;
  51.  
  52. void get(int xx , int rem , int R){
  53.     int op = 0 , pos = xx - 1;
  54.     while(rem > 0 || op > 0){
  55.         int nxtclose = *close.upper_bound(pos) , nxtopen = *open.upper_bound(pos);
  56.         if(rem == 0){
  57.             pos = nxtclose;
  58.             --op;
  59.             ans.push_back(pos);
  60.             continue;
  61.         }
  62.  
  63.         st = nxtopen , en = R;
  64.  
  65.         auto res = query(1,1,n);
  66.  
  67.         if(res.ans >= rem && res.close >= op){
  68.             pos = nxtopen;
  69.             ++op; --rem;
  70.             ans.push_back(pos);
  71.             continue;
  72.         }
  73.         else{
  74.             pos = nxtclose;
  75.             --op;
  76.             ans.push_back(pos);
  77.             continue;
  78.         }
  79.     }
  80. }
  81. int main(){
  82.     scanf("%s",ccc);
  83.     str = ccc; n = str.size();
  84.     str = "#" + str;
  85.     build(1,1,n);
  86.     for(int j = 1 ; j <= n ; j++){
  87.         if(str[j] == '(') open.insert(j);
  88.         else close.insert(j);
  89.         all.insert(j);
  90.     }
  91.     int QN;
  92.     scanf("%d",&QN);
  93.     while(QN--){
  94.         scanf("%d %d",&st,&en);
  95.         int L = query(1,1,n).ans;
  96.         //cout<<L * 2<<endl;
  97.         printf("%d\n",(L<<1));
  98.         ans.clear();
  99.         get(st , L , en);
  100.         for(auto pp : ans){
  101.             //cout<<pp<<' ';
  102.             all.erase(pp);
  103.             nk7(pp);
  104.             if(str[pp] == '(') open.erase(pp);
  105.             else close.erase(pp);
  106.         }
  107.         //puts("");
  108.  
  109.     }
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement