题解 P3215 【[HNOI2011]括号修复 / [JSOI2011]括号序列】

2019-02-04 22:56:40


既然有区间推平操作,自然就想到珂朵莉树了

之后几个操作就可以暴力维护了

就是Query操作说一下做法

我的做法是:求出 设 ( 为 1, ) 为-1

求出这个区间的前缀和

如果某个地方的前缀和小于 0 (设为S)则说明此时前面的 ')'数量多于 '(' 数量,无法匹配,此时则需要修改 修改 $\frac{-s}{2}$(上取整)个括号

同时修改前缀和(s为奇数改为1,否则为0)

最后的 若 前缀和 > 0 表示 '(' 较多,无法匹配

则还需要修改$\frac{s}{2}$个括号

#include<bits/stdc++.h>
using namespace std;

#define MAXN 100005
#define se  set<aa>
#define it iterator 

int n,m;
int a[MAXN];
char ch[MAXN];
struct aa
{
    int l,r,v;
};
bool operator <(aa a,aa b) {
    return a.r < b.r;
}
set<aa>s;

void wt()
{
    for(se::it i = s.begin(); i != s.end(); i ++)
    {
        cout<<(i->l)<<" "<<(i->r)<<" "<<(i->v)<<"\n";
    }
} 

int zh(char a)
{
    if(a == '(') return 1;
    else return -1;

}

void splix(se::it a,int i) {
    if(i < a->l) return;
    if(a->r < i+1) return;
    int sl = a->l,sr = a->r,sv = a->v;
    s.erase(a);
    s.insert((aa){sl,i,sv});
    s.insert((aa){i+1,sr,sv});
}

void fen(int l,int r)
{
    se::it x = s.lower_bound((aa){0,l,0});
    splix(x,l-1);
    se::it y = s.lower_bound((aa){0,r,0});
    splix(y,r);
}

void tuiping(int l,int r,int v)
{
    fen(l,r);
    se::it x = s.lower_bound((aa){0,l,0});
    se::it y = s.lower_bound((aa){0,r,0});
    y ++;
    s.erase(x,y);
    s.insert((aa){l,r,v});
}

aa c[MAXN];
int nn;

void tiqu(int l,int r)
{
    fen(l,r);
    se::it x = s.lower_bound((aa){0,l,0});
    se::it y = s.lower_bound((aa){0,r,0});
    nn = 0;
    for(se::it i = x; 1 == 1; i ++) {
        nn ++;
        c[nn] = (*i);
    //  cout<<nn<<":"<<c[nn].l<<" "<<c[nn].r<<" "<<c[nn].v<<"\n"; 
        if(i == y) break;
    }
} 

void Swap(int l,int r)
{
    fen(l,r);
    tiqu(l,r);
    se::it x = s.lower_bound((aa){0,l,0});
    se::it y = s.lower_bound((aa){0,r,0});
    y ++;
    s.erase(x,y);
    for(int i = 1; i <= nn; i ++) {
        s.insert((aa){r - (c[i].r - c[i].l),r,c[i].v});
        r -= (c[i].r - c[i].l)+1;
    //  cout<<r<<"\n";
    }
}

void Invert(int l,int r) {
    fen(l,r);
    tiqu(l,r);
    se::it x = s.lower_bound((aa){0,l,0});
    se::it y = s.lower_bound((aa){0,r,0});
    y ++;
    s.erase(x,y);
    for(int i = 1; i <=  nn; i ++) {
        s.insert((aa){c[i].l,c[i].r,-c[i].v});
    }   
}

void qiu(int l,int r)
{
    fen(l,r);
    tiqu(l,r);
    int ans = 0,s = 0;
    for(int i = 1; i <= nn; i ++)
    {
        s += (c[i].r - c[i].l + 1)*c[i].v;
        if(s < 0)
        {
            ans += (-s)>>1;
            if((-s)&1) 
            {
                s = 1;
                ans ++;
            }
            else s = 0;
        }
    }
    ans += abs(s)>>1; 
    printf("%d\n",ans);
}

int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",ch+1);
    for(int i = 1; i <= n; i ++) {
        if(ch[i] ==  '(' )
        {
            a[i] = 1;
            s.insert((aa){i,i,a[i]});
        }else {
            a[i] = -1;
            s.insert((aa){i,i,a[i]});
        }
    } 
//  wt();
    for(int i = 1; i <= m; i ++)
    {
        string opt;
        cin >> opt;
        if(opt == "Replace")
        {
            int l,r;
            scanf("%d%d",&l,&r);
            string ot;
            cin >> ot;
            tuiping(l,r,zh(ot[0])); 
        }
        if(opt == "Query")
        {
            int l,r;
            scanf("%d%d",&l,&r);
            qiu(l,r);
        }
        if(opt == "Swap")
        {
            int l,r;
            scanf("%d%d",&l,&r);
            Swap(l,r);
        }
        if(opt == "Invert")
        {
            int l,r;
            scanf("%d%d",&l,&r);
            Invert(l,r);
        }
    }
    return 0;
}