P10513

不知道哪里WA了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+5;

ll n,m,op,x,y;
string s;
struct node{
    ll l,r;
    ll sum,lx,rx;
    ll sum1,lx1,rx1;
    bool tag;
}tree[N*4];

void pushup(ll i){
    ll s=min(tree[i*2].lx,tree[i*2+1].rx);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum+s;
    tree[i].lx=tree[i*2].lx+tree[i*2+1].lx-s;
    tree[i].rx=tree[i*2].rx+tree[i*2+1].rx-s;
    ll st=min(tree[i*2].lx1,tree[i*2+1].rx1);
    tree[i].sum1=tree[i*2].sum1+tree[i*2+1].sum1+st;
    tree[i].lx1=tree[i*2].lx1+tree[i*2+1].lx1-st;
    tree[i].rx1=tree[i*2].rx1+tree[i*2+1].rx1-st;
}

void pushdown(ll i){
    if(tree[i].tag==0)
        return ;
    tree[i*2].tag^=1,tree[i*2+1].tag^=1;
    swap(tree[i*2].sum,tree[i*2+1].sum1);
    swap(tree[i*2+1].sum,tree[i*2+1].sum1);
    swap(tree[i*2].lx,tree[i*2].lx1);
    swap(tree[i*2+1].lx,tree[i*2+1].lx1);
    swap(tree[i*2].rx,tree[i*2+1].rx1);
    swap(tree[i*2+1].rx,tree[i*2+1].rx1);
    tree[i].tag=0;
}

void build(ll i,ll l,ll r){
    tree[i].l=l;
    tree[i].r=r;
    if(l==r){
        if(s[l]=='(')
            tree[i].lx=tree[i].rx1=1;
        else
            tree[i].rx=tree[i].lx1=1;
        return ;
    }
    ll mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    pushup(i);
    return ;
}

void change(ll i,ll l,ll r){
    if(tree[i].l>=l&&tree[i].r<=r){
        swap(tree[i].sum,tree[i].sum1);
        swap(tree[i].lx,tree[i].lx1);
        swap(tree[i].rx,tree[i].rx1);
        tree[i].tag^=1;
        return ;
    }
    pushdown(i);
    if(tree[i*2].r>=l)
        change(i*2,l,r);
    if(tree[i*2+1].l<=r)
        change(i*2+1,l,r);
    pushup(i);
    return ;
}

ll search(ll i,ll l,ll r){
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    pushdown(i);
    ll st=0;
    if(tree[i*2].r>=l)
        st+=search(i*2,l,r);
    if(tree[i*2+1].l<=r)
        st+=search(i*2+1,l,r);
    return st;
}

int main(){
    scanf("%lld",&n);
    cin>>s;
    s=" "+s;
    scanf("%lld",&m);
    build(1,1,n);
    while(m--){
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)
            change(1,x,y);
        else
            printf("%lld\n",search(1,x,y));
    }
    return 0;
}