CF1625E2 Cats on the Upgrade

· · 题解

我的博客：https://www.cnblogs.com/suxxsfe/p/15907152.html

https://www.luogu.com.cn/problem/CF1625E2

考虑把括号序列对应的树形结构建出来（按照在串中出现的顺序，给一个点所有儿子也定一个顺序）
设 u 有 son_u 个儿子，则如果不考虑只取某个儿子中的一部分作为一个合法字串的情况（也就是必须取某几个连续的儿子），那么方案数是 f_u=\dfrac{son_u\cdot (son_u+1)}{2}
再加上只取某个儿子的一部分的情况，则 u 对应的答案就是 \sum_{x\in \operatorname{subtree}(u)} f_x
那么整个询问就是求一段连续的儿子的子树 f 值和，若共有 p 个儿子，就在加上 \frac{p*(p+1)}{2}

修改的时候对 f 的影响只体现在修改点的父亲上，放在 dfs 序上就变成了单点修改区间查询，树状数组即可
考虑询问时如何确定两个兄弟节点之间有多少节点（就是求上面的 p）
对每个结点再开一个树状数组，大小为儿子个数，一开始每个儿子处都插入 1，每删掉一个儿子就把它在父亲的树状数组中的位置标成 0，区间查询即可

如果把维护 f 的树状数组换成线段树来支持区间赋值为 0，这个做法可以做修改时 s[l\cdots r] 中间不保证全为 . 的情况 

#define N 300006
#define M 600006
struct Graph{
    int fir[N],nex[M],to[M],tot;
    inline void add(int u,int v){
        to[++tot]=v;
        nex[tot]=fir[u];fir[u]=tot;
    }
    inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
}G;
int n,m;
char s[N];
int stack[N],top;
int left[N],right[N];
int L[N],R[N],id[N],tot;
void build(int u,int l,int r){
    for(int i=l+1;i<r;i++)if(right[i]){
        G.add(u,++tot);
        L[tot]=i;R[tot]=right[i];id[i]=id[right[i]]=tot;
        build(tot,i,right[i]);
        i=right[i];
    }
}
struct BIT{
    int n;
    long long *tree;
    inline void init(int size){n=size;tree=new long long[size+1];std::memset(tree,0,(size+1)*sizeof tree[0]);}
    #define lowbit(x) (x&(-x))
    inline void add(int pos,long long k){for(;pos<=n;pos+=lowbit(pos)) tree[pos]+=k;}
    inline long long ask(int pos){
        long long ret=0;
        for(;pos;pos-=lowbit(pos)) ret+=tree[pos];
        return ret;
    }
    #undef lowbit
}S,T[N];
int dfn[N],dfscnt,end[N];
int num[N],son[N],fa[N];
void dfs(int u){
    dfn[u]=++dfscnt;
    for(int i=G.fir[u];i;i=G.nex[i]) num[G.to[i]]=++son[u],fa[G.to[i]]=u,dfs(G.to[i]);
    end[u]=dfscnt;
    S.add(dfn[u],(long long)son[u]*(son[u]+1)/2);
    T[u].init(son[u]);
    for(int i=G.fir[u];i;i=G.nex[i]) T[u].add(num[G.to[i]],1);
}
int main(){
    n=read();m=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='(') stack[++top]=i;
        else if(s[i]==')'&&top) left[i]=stack[top],right[stack[top--]]=i;
    }
    tot=1;//root=1
    for(int i=1;i<=n;i++)if(right[i]){
        G.add(1,++tot);
        L[tot]=i;R[tot]=right[i];id[i]=id[right[i]]=tot;
        build(tot,i,right[i]);i=right[i];
    }
    S.init(tot);
    dfs(1);
    while(m--){
        int op=read(),l=read(),r=read();
        if(op==1){
            op=fa[id[l]];
            S.add(dfn[op],(long long)son[op]*(son[op]-1)/2-(long long)son[op]*(son[op]+1)/2);
            son[op]--;
            T[op].add(num[id[l]],-1);
        }
        else{
            l=id[l];r=id[r];op=fa[l];
            long long numl=T[op].ask(num[l]),numr=T[op].ask(num[r]);
            printf("        %lld\n",S.ask(end[l])-S.ask(dfn[r]-1)+(long long)(numl-numr+1)*(numl-numr+2)/2);
        }
    }
    return 0;
}