题解 P3767 【膜法】
LightningUZ · · 题解
总体思路是，把操作建成树，在树上求出一个操作的作用dfs序区间；对于操作的dfs序区间用线段树分治+可撤销种类并查集就可以了。
具体思路过程
如果您足够强，您就会发现这就是一堆套路拼一块
1. 只有加边
种类并查集。开五个种类维护即可。
不要忘记数组大小*5
2. 加上删除操作
考虑线段树分治+可撤销种类并查集。
线段树分治，常用于和可撤销并查集配合，离线维护一个图的连通性，以及相关信息。这个大家应该都会，不会的也不用来做这个题了。
然后可撤销的种类并查集怎么写呢？其实非常simple，和可撤销并查集的撤销部分，代码完全一样，就形如 while(top>last_top) back() 的写就可以了。加五条边也是加边，为啥就不能撤，很简单的道理。
注意我们还要在过程中维护，当前是否合法。不合法当且仅当，对于同一个元素，存在两个种类拆出来的点在同一个集合里。这显然不能每次
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)