本文共 3424 字，大约阅读时间需要 11 分钟。
题目：
离线，LCT维护删除时间最大生成树即可。注意没有被删的边的删除时间是 m+1 。
回收删掉的边的节点的话，空间就可以只开 n*2 了。
#include #include #include #include #define mkp make_pair#define ls c[x][0]#define rs c[x][1]using namespace std;int rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}const int N=1e4+5,M=5e5+5;int n,m,tot,op[M],fa[N],c[N][2],sta[N],top;int del_pl[N],del_top;bool rev[N];map ,int> mp;struct Node{ int x,y,t;}a[M];struct Dt{ int t,id,bh; Dt(int a=0,int b=0,int c=0):t(a),id(b),bh(c) {}}vl[N],mn[N];Dt Mn(Dt x,Dt y){ if(!x.t)return y; if(!y.t)return x; return (x.t cr.t)return; Node k=a[tp.id]; int bh=tp.bh; cut(k.x,bh); cut(k.y,bh); del_pl[++del_top]=bh; } int nw=New(); mn[nw]=vl[nw]=Dt(cr.t,id,nw); link(cr.x,nw); link(cr.y,nw);}int qry(int x,int y){ if(!chk(x,y))return 0; splay(x); return mn[x].t;}int main(){ n=rdn();m=rdn(); for(int i=1;i<=n;i++)mn[i]=vl[i]=Dt(0,0,0); tot=n; for(int i=1;i<=m;i++) { op[i]=rdn();int x=rdn(),y=rdn();if(x>y)swap(x,y);// if(op[i]==0)mp[mkp(x,y)]=i,a[i].x=x,a[i].y=y,a[i].t=m+1;//m+1 else if(op[i]==1)a[mp[mkp(x,y)]].t=i; else a[i].x=x,a[i].y=y; } for(int i=1;i<=m;i++) { if(op[i]==0)ins(a[i],i); if(op[i]==2)puts(qry(a[i].x,a[i].y)>i?"Y":"N"); } return 0;}
或者可以线段树分治。
线段树分治就是离线，按操作时间建一个线段树，把修改放在树上，然后遍历线段树，支持修改的栈序撤销，走到叶子就可以知道那个时刻的答案。
这道题就是给线段树节点开 vector 存它有些什么边，然后并查集按秩合并，就可以栈序撤销了。
比 LCT 快了一倍。
#include #include #include #include #include #define ls Ls[cr]#define rs Rs[cr]#define pb push_back#define mkp make_pairusing namespace std;int rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}const int N=5005,M=5e5+5,K=20;int n,m,op[M],fa[N],siz[N],top; bool vis[M],ans[M];int tot,Ls[M<<1],Rs[M<<1],sm[M<<1];struct Node{ int x,y; Node(int x=0,int y=0):x(x),y(y) {}}a[M],sta[N];vector vt[M<<1];map ,int> mp;void build(int l,int r,int cr){ if(l==r)return; int mid=l+r>>1; ls=++tot; build(l,mid,ls); rs=++tot; build(mid+1,r,rs);}void ins(int l,int r,int cr,int L,int R,Node k){ if(l>=L&&r<=R){vt[cr].pb(k);return;} int mid=l+r>>1; if(L<=mid)ins(l,mid,ls,L,R,k); if(mid >1; cz(l,mid,ls); cz(mid+1,r,rs); sm[cr]=sm[ls]+sm[rs];}int fnd(int a){ return fa[a]==a?a:fnd(fa[a]);}void mrg(Node a){ int x=fnd(a.x),y=fnd(a.y); if(x==y)return; if(siz[x] >1; if(sm[ls]) { int nw=top; solve(l,mid,ls); for(int& i=top;i>nw;i--) { int x=sta[i].x,y=sta[i].y; fa[x]=x; siz[y]-=siz[x]; } } if(sm[rs]) { int nw=top; solve(mid+1,r,rs); for(int& i=top;i>nw;i--) { int x=sta[i].x,y=sta[i].y; fa[x]=x; siz[y]-=siz[x]; } }}int main(){ n=rdn();m=rdn(); tot=1;build(1,m,1); for(int i=1;i<=m;i++) { op[i]=rdn();int x=rdn(),y=rdn(); if(x>y)swap(x,y);// if(!op[i]) { a[i]=Node(x,y); mp[mkp(x,y)]=i; } else if(op[i]==1) { int bh=mp[mkp(x,y)]; vis[bh]=1; ins(1,m,1,bh,i-1,a[bh]); } else a[i]=Node(x,y); } for(int i=1;i<=m;i++) if(!op[i]&&!vis[i])ins(1,m,1,i,m,a[i]); cz(1,m,1); for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1; solve(1,m,1); for(int i=1;i<=m;i++) if(op[i]==2)puts(ans[i]?"Y":"N"); return 0;}
转载于:https://www.cnblogs.com/Narh/p/10372004.html
