自动搬运

查看原文

来自洛谷，原作者为

	LightningUZ 关注嘉然，顿顿解馋！

搬运于2025-08-24 21:52:29，当前版本为作者最后更新于2020-12-16 23:07:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

总体思路是，把操作建成树，在树上求出一个操作的作用dfs序区间；对于操作的dfs序区间用线段树分治+可撤销种类并查集就可以了。

具体思路过程

如果您足够强，您就会发现这就是一堆套路拼一块

1. 只有加边

种类并查集。开五个种类维护即可。

不要忘记数组大小*5

2. 加上删除操作

考虑线段树分治+可撤销种类并查集。

线段树分治，常用于和可撤销并查集配合，离线维护一个图的连通性，以及相关信息。这个大家应该都会，不会的也不用来做这个题了。

然后可撤销的种类并查集怎么写呢？其实非常simple，和可撤销并查集的撤销部分，代码完全一样，就形如 while(top>last_top) back() 的写就可以了。加五条边也是加边，为啥就不能撤，很简单的道理。

注意我们还要在过程中维护，当前是否合法。不合法当且仅当，对于同一个元素，存在两个种类拆出来的点在同一个集合里。这显然不能每次 $O(n)$ 求，但是注意到每次改两个关系，只会对这两个点有影响，$O(1)$ 的 check 一下这两个点是否合法就行。然后维护一个全局变量，表示当前是否合法。注意这个全局变量的值，也要记在撤销信息的 struct 中（撤销的时候，这个变量的值也要相应的被改变，显然）。

3. 加上历史版本

每个操作都有其依赖的版本，除了初始节点0。很容易联想到这是一个树形结构。把树建出来。

和序列类似，考虑一个操作的影响区间，应该是子树-若干个子子树（子子树定义为，子树中某个点的子树）。考虑它的dfs序，就是一段区间-若干个子区间。

那么我们可以枚举每一个删除操作，然后把它删除的那个点的影响区间分裂成两部分。关于具体咋实现，就是维护一下当前区间的左端点 mx，然后对于删除操作的dfs序区间为 [l,r]，加上影响区间 [mx,l-1]，然后更新 mx=r+1 即可。到最后在加上 [mx,odfn]，odfn就是子树的dfs序区间右端点（代码里就是这个名称）

最后在dfs序区间上跑线段树分治就行了。别忘记最后输出的是 ans[dfn[i]]，而不是 ans[i]。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 200005
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define all(a) a.begin(),a.end()
    #define iter(a,p) (a.begin()+p)
    int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
    template <typename T> void Rd(T& arg){arg=I();}
    template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}
    void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}

    int n,m;
    struct add{int t,u,v;}; // 加的一个条件（t=1生，t=2克）
    struct query{int fa; add e;}o[N]; // 一个操作（如果是删除操作，令e.u=删除的位置）
    void Input()
    {
        Rd(n,m);
        F(i,1,m)
        {
            int f,t; Rd(f,t);
            o[i].fa=f; o[i].e.t=t;
            switch(t)
            {
                case 1: 
                case 2: {o[i].e.u=I(); o[i].e.v=I(); break;}
                case 3: {o[i].e.u=I(); break;}
            }
        }
    }
    class Graph // 存储图的类
    {
    public:
        int head[N];
        struct edge{int u,v,nx;}; vector<edge> E;
        inline void adde(int u,int v)
        {
            E.p_b((edge){u,v,head[u]}); head[u]=sz(E)-1;
        }
        inline void add2(int u,int v) {adde(u,v),adde(v,u);}
        inline int  st(int u) {return u==-1?-1:head[u];}
        inline int  nx(int i) {return i==-1?-1:E[i].nx;}
        inline int  to(int i) {return i==-1?-1:E[i].v;}
        inline vector<edge> adds() {return E;}
        inline void clear() {E.clear(); MEM(head,-1);}
        Graph() {clear();}
    }G;
    class Union_Find_Back_Type // 可撤销种类并查集
    {
    public:
        int fa[N*5],sz[N*5]; bool vis[N*5]; // 五倍空间
        bool is_legal; // 当前是否合法
        struct bak{int u,v,fv,su; bool legal;} bk[N*5]; int top=0; // 把当前是否合法也要记下
        int P[N][5],tot;
        
        void clear(int n) 
        {
            tot=0;
            F(i,1,n) F(j,0,4) P[i][j]=++tot; 
            is_legal=1;

            F(i,1,tot) fa[i]=i,sz[i]=1,vis[i]=0; // 这里循环到tot （写5*n也可以）
            while(top) bk[top--]=(bak){0,0,0,0,0};
        }
        int  find(int x) {return x==fa[x]?x:find(fa[x]);}
        void merge(int u,int v)
        {
            u=find(u),v=find(v);
            if (u==v) return;
            if (sz[u]<sz[v]) swap(u,v);
            bk[++top]=(bak){u,v,fa[v],sz[u],is_legal};
            fa[v]=u; sz[u]+=sz[v];
        }
        bool same(int u,int v) {return find(u)==find(v);}
        bool illegal(int u) // 判断u是否不合法了
        {
            F(i,0,4) vis[find(P[u][i])]=0;
            F(i,0,4) 
            {
                int f=find(P[u][i]);
                if (vis[f]) return true;
                vis[f]=1;
            }
            return false;
        }
        void ke(int u,int v) // 克
        {
            F(j,0,4) merge(P[u][j],P[v][(j+2)%5]);
            if (illegal(u) or illegal(v)) is_legal=0;
            // 每次更新一下u,v即可
        }
        void sh(int u,int v) // 生
        {
            F(j,0,4) merge(P[u][j],P[v][(j+1)%5]);
            if (illegal(u) or illegal(v)) is_legal=0;
        }
        void addtype(add e)
        {
            if (e.t==1) sh(e.u,e.v);
            else        ke(e.u,e.v);
        }
        void back() // 撤销一次
        {
            bak tmp=bk[top--];
            int u=tmp.u,v=tmp.v;
            fa[v]=tmp.fv; sz[u]=tmp.su;
            is_legal=tmp.legal;
        }
    }un;
    int ans[N];
    class SegmentTree // 非常板子
    {
    public:
        vector<add> es[N<<2];
        #define ls ix<<1
        #define rs ix<<1|1
        #define lson ls,L,mid
        #define rson rs,mid+1,R
        #define inx int ix=1,int L=1,int R=(m+1)
        void adde(int l,int r,add e,inx)
        {
            if (l>r) return;
            if (l<=L and R<=r)
            {
                es[ix].p_b(e);
                return;
            }
            int mid=(L+R)>>1;
            if (l<=mid) adde(l,r,e,lson);
            if (mid<r)  adde(l,r,e,rson);
        }
        void solve(inx)
        {
            int rec=un.top;
            for(auto e:es[ix]) un.addtype(e);
            if (L==R)
            {
                ans[L]=un.is_legal;
            }
            else
            {
                int mid=(L+R)>>1;
                solve(lson); solve(rson);
            }
            while(un.top>rec) un.back();
        }
    }T;

    int idfn[N],odfn[N],tick=0;
    void DFS_init(int u) // 先处理出dfs序区间
    {
        idfn[u]=++tick;
        Tra(i,u) DFS_init(v);
        odfn[u]=tick;
    }
    int mx[N];
    void DFS(int u)
    {
        if (o[u].e.t==3) // 对于删除操作，更新一下影响区间
        {
            int p=o[u].e.u;
            T.adde(mx[p],idfn[u]-1,o[p].e);
            mx[p]=odfn[u]+1;
        }
        Tra(i,u) DFS(v);
    }
    void Soviet()
    {
        G.clear();
        F(i,1,m) G.adde(o[i].fa,i); // 加边

        DFS_init(0);
        F(i,0,m) mx[i]=idfn[i];

        DFS(0);
        F(i,1,m) if (o[i].e.t!=3) T.adde(mx[i],odfn[i],o[i].e);
        // 这些就是上面提到的处理一个区间中删除了若干的子区间的方法
        /*
        就是，维护一下当前区间的左端点 mx
        然后对于删除操作的dfs序区间为 [l,r]，加上影响区间 [mx,l-1]，然后更新 mx=r+1 即可。
        到最后在加上 [mx,odfn]，odfn就是子树的dfs序区间右端点
        （代码里就是这个名称）
        */

        un.clear(n);
        T.solve();
        F(i,1,m) puts(ans[idfn[i]]?"excited":"naive");
    }
    void IsMyWife()
    {
        Input();
        Soviet();
    }
}
#undef int //long long
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();
    return 0;
}

PS: 神奇的是，最长的不是线段树分治 (约1KB)，而是可撤销种类并查集 (约2KB)