Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long long MX = (1<<19);
- struct node{
- int open , close , ans;
- node(){
- open = close = ans = 0;
- }
- node(int open , int close , int ans):open(open) , close(close) , ans(ans){}
- }tree[MX*4];
- string str;
- int idx[MX];
- node merge_(node L , node R){
- node ret = node(L.open + R.open , L.close + R.close , L.ans + R.ans);
- int add = min(L.open , R.close);
- ret.open -= add;
- ret.close -= add;
- ret.ans += add;
- return ret;
- }
- void build(int x , int a , int b){
- if(a == b){
- idx[a] = x;
- if(str[a] == '(')
- tree[x] = node(1 , 0 , 0);
- else tree[x] = node(0 , 1 , 0);
- return;
- }
- build(x*2 , a , (a+b)/2);
- build(x*2+1 , (a+b)/2+1 ,b);
- tree[x] = merge_(tree[x*2] , tree[x*2+1]);
- }
- void nk7(int x){
- x = idx[x]; tree[x] = node();
- x >>= 1;
- while(x > 0){
- tree[x] = merge_(tree[x*2] , tree[x*2+1]);
- x >>= 1;
- }
- }
- int st , en;
- node query(int x , int a , int b){
- if(st > b || en < a) return node();
- if(a >= st && b <= en) return tree[x];
- return merge_(query(x*2 , a ,(a+b)/2) , query(x*2+1 , (a+b)/2+1 , b));
- }
- char ccc[MX];
- int n;
- set < int > open , close , all;
- vector < int > ans;
- void get(int xx , int rem , int R){
- int op = 0 , pos = xx - 1;
- while(rem > 0 || op > 0){
- int nxtclose = *close.upper_bound(pos) , nxtopen = *open.upper_bound(pos);
- if(rem == 0){
- pos = nxtclose;
- --op;
- ans.push_back(pos);
- continue;
- }
- st = nxtopen , en = R;
- auto res = query(1,1,n);
- if(res.ans >= rem && res.close >= op){
- pos = nxtopen;
- ++op; --rem;
- ans.push_back(pos);
- continue;
- }
- else{
- pos = nxtclose;
- --op;
- ans.push_back(pos);
- continue;
- }
- }
- }
- int main(){
- scanf("%s",ccc);
- str = ccc; n = str.size();
- str = "#" + str;
- build(1,1,n);
- for(int j = 1 ; j <= n ; j++){
- if(str[j] == '(') open.insert(j);
- else close.insert(j);
- all.insert(j);
- }
- int QN;
- scanf("%d",&QN);
- while(QN--){
- scanf("%d %d",&st,&en);
- int L = query(1,1,n).ans;
- //cout<<L * 2<<endl;
- printf("%d\n",(L<<1));
- ans.clear();
- get(st , L , en);
- for(auto pp : ans){
- //cout<<pp<<' ';
- all.erase(pp);
- nk7(pp);
- if(str[pp] == '(') open.erase(pp);
- else close.erase(pp);
- }
- //puts("");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement