題目：https://loj.ac/problem/121

離線，LCT維護刪除時間最大生成樹即可。注意沒有被刪的邊的刪除時間是 m+1 。

回收刪掉的邊的節點的話，空間就可以只開 n*2 了。

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #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<pair<int,int>,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<y.t)?x:y; } int New() {int ret=(del_top?del_pl[del_top--]:++tot);c[ret][0]=c[ret][1]=fa[ret]=0; return ret; } bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} void pshp(int x){mn[x]=Mn(vl[x],Mn(mn[ls],mn[rs]));} void Rev(int x) {if(!rev[x])return; rev[x]=0;rev[ls]^=1; rev[rs]^=1; swap(ls,rs); } void rotate(int x) {int y=fa[x],z=fa[y],d=(x==c[y][1]);if(!isroot(y))c[z][y==c[z][1]]=x;fa[x]=z;fa[y]=x; fa[c[x][!d]]=y;c[y][d]=c[x][!d]; c[x][!d]=y;pshp(y); pshp(x); } void splay(int x) {sta[top=1]=x;for(int k=x;!isroot(k);k=fa[k])sta[++top]=fa[k];for(int i=top;i;i--)Rev(sta[i]);while(!isroot(x)){int y=fa[x],z=fa[y];if(!isroot(y))((x==c[y][0])^(y==c[z][0]))?rotate(x):rotate(y);rotate(x);} } void access(int x) {for(int t=0;x;rs=t,pshp(x),t=x,x=fa[x])splay(x); } void mkrt(int x) {access(x);splay(x);rev[x]^=1; } void link(int x,int y) {mkrt(x); fa[x]=y; } void cut(int x,int y) {mkrt(x); access(y); splay(y);c[y][0]=0; pshp(y); fa[x]=0; } bool chk(int x,int y) {mkrt(x); access(y); splay(y);while(c[y][0])y=c[y][0];return x==y; } void ins(Node cr,int id) {int x=cr.x,y=cr.y;if(chk(x,y)){splay(x);Dt tp=mn[x]; if(tp.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+1else 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; } View Code

?或者可以線段樹分治。

線段樹分治就是離線，按操作時間建一個線段樹，把修改放在樹上，然后遍歷線段樹，支持修改的棧序撤銷，走到葉子就可以知道那個時刻的答案。

這道題就是給線段樹節點開 vector 存它有些什么邊，然后并查集按秩合并，就可以棧序撤銷了。

比 LCT 快了一倍。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<map> #define ls Ls[cr] #define rs Rs[cr] #define pb push_back #define mkp make_pair 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=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<Node> vt[M<<1]; map<pair<int,int>,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<R)ins(mid+1,r,rs,L,R,k); } void cz(int l,int r,int cr) {if(l==r){sm[cr]=(op[l]==2?1:0);return;}int mid=l+r>>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]<siz[y])swap(x,y);sta[++top]=Node(y,x); fa[y]=x; siz[x]+=siz[y]; } void solve(int l,int r,int cr) {int sz=vt[cr].size();for(int i=0;i<sz;i++)mrg(vt[cr][i]);if(l==r){ans[l]=(fnd(a[l].x)==fnd(a[l].y));return;}int mid=l+r>>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; } View Code

?

轉載于:https://www.cnblogs.com/Narh/p/10372004.html

總結

以上是生活随笔為你收集整理的LOJ 121 「离线可过」动态图连通性——LCT维护删除时间最大生成树 / 线段树分治...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。