题解：CF2104G Modulo 3

· · 题解

题目分析

首先我们发现，一个环上的点一定会被染成一种颜色。 所以我们考虑先缩一下点。

那么现在一定是一个 DAG。然后我们发现只要按照拓扑序染色，那么每个点想是什么颜色就能是什么颜色。

设 DAG 上的点个数为 cnt，颜色数为 k，那么答案为 k^{cnt}。

由于原图每个点只有一条出边，所以强连通分量只能是一个环，且每个点最多在一个环里出现。

问题转化成统计图上环的数量。

还是由于每个点只有一条出边，我们可以把有向边看成无向边。

那么维护连通块修改不是很方便，所以我们先用线段树分治变成只加边。

但是在加入一条边 (x,y) 且 x,y 联通时，我们就需要查询 x,y 的树上距离。这一步当然可以 LCT 做，但是我们还没用到题目中模 3 的性质。

在答案统计中，点数是放在指数上的，根据欧拉定理，它应该是模 2。

所以距离只有 0 和 1 两种，在此基础下异或跟加减法的结果一样，所以直接用带权并查集即可。

时间复杂度 O(n\log^2 n)。

顺带一提，可以 LCT 维护基环树，做到 O(n\log n)。

Code

就放 LCT 维护基环树了。

#include<bits/stdc++.h>
using namespace std;
//
const int maxn=2e5+10;
const int mod=3;
int n,q;
int to[maxn];
int vis[maxn];
int res;
inline int Pow(int x,int y){
    x%=mod;
    int s=1;
    for(;y;x=x*x%mod,y>>=1)if(y&1)s=s*x%mod;
    return s;
}
struct node{
    int fa,son[2];
    int sz,val;
    int tagr,tagm;
    node(){fa=son[0]=son[1]=sz=val=tagr=0,tagm=-1;}
}tree[maxn];
inline void init(){for(int i=1;i<=n;i++)tree[i].sz=1;}
inline int isroot(int v){return v!=tree[tree[v].fa].son[0]&&v!=tree[tree[v].fa].son[1];}
inline int get(int v){return v==tree[tree[v].fa].son[1];}
inline void connect(int f,int v,int type){tree[f].son[type]=v;if(v)tree[v].fa=f;}
inline void pushup(int v){
    tree[v].sz=tree[tree[v].son[0]].sz+tree[tree[v].son[1]].sz+1;
}
inline void reverse(int v){
    swap(tree[v].son[0],tree[v].son[1]);
    tree[v].tagr^=1;
}
inline void modify(int v,int k){
    tree[v].val=k;
    tree[v].tagm=k;
}
inline void pushdown(int v){
    if(tree[v].tagr){
        reverse(tree[v].son[0]);
        reverse(tree[v].son[1]);
        tree[v].tagr=0;
    }
    if(tree[v].tagm!=-1){
        modify(tree[v].son[0],tree[v].tagm);
        modify(tree[v].son[1],tree[v].tagm);
        tree[v].tagm=-1;
    }
}
inline void pushtag(int v){if(!isroot(v))pushtag(tree[v].fa);pushdown(v);}
inline void rotate(int v){
    int f=tree[v].fa,g=tree[f].fa,chk=get(v);
    if(!isroot(f))tree[g].son[get(f)]=v;
    tree[v].fa=g;
    connect(f,tree[v].son[chk^1],chk);
    connect(v,f,chk^1);
    pushup(f);
    pushup(v);
}
inline void splay(int v){
    pushtag(v);
    while(!isroot(v)){
        int f=tree[v].fa;
        if(!isroot(f))rotate(get(f)==get(v)?f:v);
        rotate(v);
    }
}
inline void access(int v){
    int p=0;
    while(v){
        splay(v);
        tree[v].son[1]=p;
        pushup(v);
        p=v,v=tree[v].fa;
    }
}
inline void mkroot(int v){
    access(v);
    splay(v);
    reverse(v);
}
inline int findroot(int v){
    access(v);
    splay(v);
    while(tree[v].son[0])v=tree[v].son[0];
    splay(v);
    return v;
}
inline void split(int x,int y){
    mkroot(x);
    access(y);
    splay(y);
}
inline void link(int x,int y){
    mkroot(x),mkroot(y);
    tree[x].fa=y;
}
inline void cut(int x,int y){
    split(x,y);
    tree[y].son[0]=tree[x].fa=0;
    pushup(y);
}
inline int ask(int x){
    access(x),splay(x);
    return tree[x].val;
}
inline void insert(int p){
    int x=p,y=to[p];
    if(findroot(x)!=findroot(y))link(x,y);
    else{
        split(x,y);
        res-=tree[y].sz-1;
        modify(y,p);
        vis[p]=1;
    }
}
inline void delet(int p){
    int x=p,y=to[p];
    if(vis[p]){
        split(x,y);
        res+=tree[y].sz-1;
        modify(y,0);
        vis[p]=0;       
    }else if(ask(y)==ask(x)&&ask(x)){
        p=ask(x);
        split(p,to[p]);
        res+=tree[to[p]].sz-1;
        modify(to[p],0);
        vis[p]=0;
        cut(x,y);
        link(p,to[p]);
    }else cut(x,y);
}
int main(){
    cin>>n>>q;
    init();
    res=n;
    for(int i=1;i<=n;i++){
        cin>>to[i];
        insert(i);
    }
    while(q--){
        int x,y,k;
        cin>>x>>y>>k;
        delet(x);
        to[x]=y;
        insert(x);
        cout<<Pow(k,res)<<'\n';
    }

    return 0;
}