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

· · 题解

首先，设 ( = -1，) = 1，定义 \text{prmax} 为前缀最大值，\text{sfmin} 为后缀最小值，那么一个区间的答案为

\lceil \text{prmax}/2\rceil+\lceil|\text{sfmin}|/2\rceil

要维护答案，考虑众所周知的 线段树/平衡树 五问：
(跟 zyb 学的)

1、每个节点需要记录哪些信息？

要记录区间和，前缀最大、最小，后缀最大、最小。

2、需要哪些标记？

只需要题目中的三种操作标记即可。

3、如何下传标记？

先来考虑标记优先级：取反、覆盖、翻转。

打取反标记时，区间和、节点值直接取反；\text{prmax} 变 -\text{prmin}，\text{prmin} 变 -\text{prmax}，对于后缀同理。别忘了还要对覆盖标记取反。

对于覆盖标记，若赋值为正数，\text{prmax,sfmax} 变区间和，\text{prmin,sfmin} 变为 0。对于赋值为负数同理。

翻转标记比较简单，除了交换左右儿子，再交换前缀、后缀的最大最小和即可。

4、如何对区间整体修改？

这个没什么好说的，直接在对应区间的子树根上打标记即可。

5、如何合并区间 (上传信息)？

这里可以参考 GSS1 传标记的做法，也就是这样：

prmax[u] = max(prmax[ls],sum[ls]+a[u]+prmax[rs]);
prmin[u] = min(prmin[ls],sum[ls]+a[u]+prmin[rs]);
sfmax[u] = max(sfmax[rs],sum[rs]+a[u]+sfmax[ls]);
sfmin[u] = min(sfmin[rs],sum[rs]+a[u]+sfmin[ls]);

这里 ls 和 rs 分别指左右儿子。 解决了上面五问，整个题就解决啦。

参考代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define reg register
#define N 100003
#define ls son[u][0]
#define rs son[u][1]
using namespace std;

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

int n,q;

struct fhqTreap{
    int a[N],son[N][2],rnd[N],sum[N],sfmax[N],sfmin[N];
    int tag[N],size[N],prmax[N],prmin[N];
    bool rev[N],inv[N];
    int rt,cnt;

    inline int neww(int x){
        int u = ++cnt;
        sum[u] = a[u] = x;
        if(x==1) prmax[u] = sfmax[u] = 1;
        else sfmin[u] = prmin[u] = -1;
        size[u] = 1;
        rnd[u] = rand();
        return u;
    }

    inline void pushup(int u){
        sum[u] = sum[ls]+sum[rs]+a[u];
        size[u] = size[ls]+size[rs]+1;
        prmax[u] = max(prmax[ls],sum[ls]+a[u]+prmax[rs]);
        prmin[u] = min(prmin[ls],sum[ls]+a[u]+prmin[rs]);
        sfmax[u] = max(sfmax[rs],sum[rs]+a[u]+sfmax[ls]);
        sfmin[u] = min(sfmin[rs],sum[rs]+a[u]+sfmin[ls]);
    }

    inline void pushr(int u){
        swap(ls,rs);
        swap(prmax[u],sfmax[u]);
        swap(prmin[u],sfmin[u]);
        rev[u] ^= 1;
    }

    inline void pushiv(int u){
        a[u] = -a[u];
        sum[u] = -sum[u];
        int x = prmax[u],y = prmin[u];
        prmin[u] = -x,prmax[u] = -y;
        x = sfmax[u],y = sfmin[u];
        sfmin[u] = -x,sfmax[u] = -y;
        inv[u] ^= 1;
        tag[u] = -tag[u];
    }

    inline void pushc(int u,int k){
        a[u] = tag[u] = k;
        sum[u] = size[u]*k;
        if(k==1){
            prmin[u] = sfmin[u] = 0;
            prmax[u] = sfmax[u] = sum[u];
        }else{
            prmax[u] = sfmax[u] = 0;
            prmin[u] = sfmin[u] = sum[u];
        }
    }

    inline void pushdown(int u){
        if(inv[u]){
            if(ls) pushiv(ls);
            if(rs) pushiv(rs);
            inv[u] = 0;
        }
        if(tag[u]){
            if(ls) pushc(ls,tag[u]);
            if(rs) pushc(rs,tag[u]);
            tag[u] = 0;
        }
        if(!rev[u]) return;
        if(ls) pushr(ls);
        if(rs) pushr(rs);
        rev[u] = 0;
    }

    int merge(int u,int v){
        pushdown(u);
        pushdown(v);
        if(!u||!v) return u|v;
        if(rnd[u]<rnd[v]){
            son[u][1] = merge(son[u][1],v);
            pushup(u);
            return u;
        }else{
            son[v][0] = merge(u,son[v][0]);
            pushup(v);
            return v;
        }
    }

    void split(int cur,int k,int &u,int &v){
        if(!cur){
            u = v = 0;
            return;
        }
        pushdown(cur);
        if(size[son[cur][0]]<k){
            u = cur;
            split(son[u][1],k-size[ls]-1,son[u][1],v);
        }else{
            v = cur;
            split(son[v][0],k,u,son[v][0]);
        }
        pushup(cur);
    }

    inline void push_back(int x){
        rt = merge(rt,neww(x));
    }

    inline int query(int l,int r){
        int x,y,z,t,res;
        split(rt,l-1,x,y);
        split(y,r-l+1,y,z);
        t = prmax[y];
        res = (t&1)?(t>>1)+1:(t>>1);
        t = abs(sfmin[y]);
        res += (t&1)?(t>>1)+1:(t>>1);
        rt = merge(merge(x,y),z);
        return res;
    }

    inline void reverse(int l,int r){
        int x,y,z;
        split(rt,l-1,x,y);
        split(y,r-l+1,y,z);
        pushr(y);
        rt = merge(merge(x,y),z);
    }

    inline void replace(int l,int r,int k){
        int x,y,z;
        split(rt,l-1,x,y);
        split(y,r-l+1,y,z);
        pushc(y,k);
        rt = merge(merge(x,y),z);
    }

    inline void invert(int l,int r){
        int x,y,z;
        split(rt,l-1,x,y);
        split(y,r-l+1,y,z);
        pushiv(y);
        rt = merge(merge(x,y),z);
    }

    void dfs(int u){
        pushdown(u);
        if(ls) dfs(ls);
        printf("%d ",a[u]);
        if(rs) dfs(rs);
    }
}T;

inline bool check(char c){
    return (c>='a'&&c<='z')||(c>='A'&&c<='Z');
}

int main(){
    srand(time(0));
    int l,r,k;
    read(n),read(q);
    char op,c = getchar();
    while(c!='('&&c!=')') c = getchar();
    while(c=='('||c==')'){
        T.push_back(c==')'?1:-1);
        c = getchar();
    }
    while(q--){
        c = getchar();
        while(!check(c)) c = getchar();
        op = c;
        while(check(c)) c = getchar();
        read(l),read(r);
        if(op=='R'){
            c = getchar();
            while(c!='('&&c!=')') c = getchar();
            k = c==')'?1:-1;
        }
        if(op=='R') T.replace(l,r,k);
        else if(op=='S') T.reverse(l,r);
        else if(op=='I') T.invert(l,r);
        else printf("%d\n",T.query(l,r));
    }
    return 0;
}