题解：P7826 「RdOI R3」RBT

· · 题解

螳臂题面，“什么都不做”指颜色也不染。但开头就直接说染成蓝色。

补充之前题解的内容。

题目上的“出现次数为奇数”和 p 的数据范围就差把 bitset 写题目上了。上线段树，除了操作 3 其他都是容易的：循环位移、单修、异或。

发现操作 3 很搞笑，如果我们刚开始把一个点的儿子从小到大排序来跑 dfs 序，则操作 3 只会改变兄弟的子树大小，除此之外全部不变。所以我们可以用 set 维护一个点儿子的集合，操作一个点时，就在其父亲的 set 里找前驱，改变前驱的子树大小，再从 set 删除当前点就行。于是是在线的。

注意预处理 i^k。注意 bitset 左移溢出 p 的部分需要消掉，不然后面可能会右移回来。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=998244353;
int n,q,P,k,a[N],w[N],f[N];
inline int pw(int x,int y){
    int ans=1;
    for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ans=1ll*ans*x%mod;
    return ans;
}
set<int> S[N];
int dfn[N],low[N],idx,xl[N];
void dfs(int p,int fa){
    if(f[p]=fa) S[p].erase(fa);
    xl[dfn[p]=++idx]=p;
    for(int v:S[p]) dfs(v,p);
    low[p]=idx;
}
bitset<500> base;
struct Tree{
    int tag;
    bitset<500> S;
}t[1<<18];
#define mid ((l+r)>>1)
void build(int p,int l,int r){
    if(l==r){
        t[p].S[a[xl[l]]]=1;
        return;
    }
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    t[p].S=t[2*p].S^t[2*p+1].S;
}
inline void ins(int p,int v){
    (t[p].tag+=v)%=P;
    t[p].S=((t[p].S<<v)&base)|(t[p].S>>(P-v));
}
inline void pushdown(int p){
    if(t[p].tag){
        ins(2*p,t[p].tag);
        ins(2*p+1,t[p].tag);
        t[p].tag=0;
    }
}
void change(int p,int l,int r,int lt,int rt,int v){
    if(lt<=l&&r<=rt) return ins(p,v),void();
    pushdown(p);
    if(lt<=mid) change(2*p,l,mid,lt,rt,v);
    if(mid<rt) change(2*p+1,mid+1,r,lt,rt,v);
    t[p].S=t[2*p].S^t[2*p+1].S;
}
void change(int p,int l,int r,int x,int v){
    if(l==r){
        t[p].S.reset();
        t[p].S[v]=1;
        return;
    }
    pushdown(p); 
    if(x<=mid) change(2*p,l,mid,x,v);
    else change(2*p+1,mid+1,r,x,v);
    t[p].S=t[2*p].S^t[2*p+1].S;
}
bitset<500> query(int p,int l,int r,int lt,int rt){
    if(lt<=l&&r<=rt) return t[p].S;
    pushdown(p);
    if(lt<=mid&&mid<rt) return query(2*p,l,mid,lt,rt)^query(2*p+1,mid+1,r,lt,rt);
    return lt<=mid?query(2*p,l,mid,lt,rt):query(2*p+1,mid+1,r,lt,rt);
}
int main(){
    read(n),read(q),read(P),read(k);
    for(int i=0;i<P;++i) w[i]=pw(i,k);
    for(int i=0;i<P;++i) base[i]=1;
    for(int i=1;i<=n;++i) read(a[i]);
    for(int i=1;i<n;++i){
        int x,y;
        read(x),read(y);
        S[x].insert(y);
        S[y].insert(x); 
    }
    dfs(1,0);
    build(1,1,n);
    while(q--){
        int op,x;
        read(op),read(x);
        if(op==1){
            int v;read(v);
            change(1,1,n,dfn[x],low[x],v);
        }
        if(op==2){
            int v;read(v);
            change(1,1,n,dfn[x],v);
        }
        if(op==3){
            if(x==1) continue;
            auto it=S[f[x]].find(x);
            if(it!=S[f[x]].begin()) low[*(--it)]=low[x],S[f[x]].erase(x);
        }
        if(op==4){
            auto s=query(1,1,n,dfn[x],low[x]);
            long long ans=0;
            for(int i=0;i<P;++i) if(s[i]) ans+=w[i];
            print(ans%mod),pc('\n');
        }
    }
    flush();
    return 0;
}