loj#122.「强制在线」动态图连通性 - 好文

<>loj#122. 「强制在线」动态图连通性 <https://loj.ac/problem/122>

UPD：（7个月以后）这代码被叉了，我不想改了（
negii真dl
然后发现这格式一更新…啊我的公式和链接怎么假掉了（
csdn[]
算了不管了…反正这样子的话之后也不会用了（

题意
N 个点，M 次操作，支持加边/删边/询问两点间连通性。强制在线。
背景
来看题的请向下翻一段。我挂一个人…。要不是这个人我绝对不会写这东西…

截消息记录…大概…算是…经过许可？
不行再删掉好了。

题解
板子题。思考再三觉得自己还是不要写题解了… 任何可以被找到的资料…比如
[这个](http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf) …都比我说得明白。
实现细节
当然选择ETT而不是学习neither写LCT了（雾本来可以写只记边不记点的那种？但是想起这一点的时候已经写了一半，懒得改了…
存边用的邻接矩阵，也没写内存回收。空间1个G，随便开啊，真良心。理论上给边升级的那个dfs应该写找到一个转一次的吧…但我太懒了就没写（？
对着数据调的，大部分数据挺弱…一直处于【这里写的什么鬼东西啊为什么还能过那么多点】的状态。所以对于自己的代码是否有致命错误表示怀疑
我好像真不知道瞎打标记会不会对复杂度造成奇怪的影响
代码
本来写题过程中注释不是中文的。写博客的时候考虑到自己只能意会的辣鸡英语水平就改成中文了 #include<bits/stdc++.h> #define
N 16800000//节点数（5e5x2x16+5000x16） #define M 1000006//边数 using namespace std;
char ch; inline void rd(int &x) { for(;(ch=getchar()-'0')<0||ch>9;);
for(x=ch;(ch=getchar()-'0')>=0&&ch<=9; x=(x<<3)+(x<<1)+ch); } bool
intr[M],del[N],gdel[N]; //intr:是否为树边 del/gdel:图中的删除标记 int
n,m,lev[M],hd[M][16],//hd:边到它每层对应节点编号的映射 Nxt[N],To[N],//记录每个点挂着的树边的链表
gt,et=1,mp[5003][5003],nxt[N],to[N],//记录非树边的链表
c[N][2],f[N],se[N],st[N],Se[N],St[N];//ETT的一些节点信息 //se:树边数量 st:树边和非树边数量
Se/St:子树信息和 inline void upd(int x) { Se[x]=se[x]+Se[c[x][0]]+Se[c[x][1]],
St[x]=st[x]+St[c[x][0]]+St[c[x][1]]; } inline void rotate(int x,bool t) {
register int y=f[x]; f[y]?c[f[y]][c[f[y]][1]==y]=x:0;
f[x]=f[y],c[y][t^1]=c[x][t]; f[c[x][t]]=y,c[x][t]=y,f[y]=x; upd(y),upd(x); }
inline void splay(int x,int to) { int y;bool t1,t2; while(f[x]^to) {
t1=c[y=f[x]][0]==x,t2=c[f[y]][0]==y; if(f[y]==to) {rotate(x,t1);return;}
t1^t2?rotate(x,t1):rotate(y,t2); rotate(x,t2); } } inline void Gins(int u,int
v,int l)//在G(l)里插入(u->v) { hd[mp[u][v]][l]=++gt; u=l*n+u;
splay(u,0),st[u]++,upd(u); nxt[gt]=nxt[u],nxt[u]=gt,to[gt]=v; } inline void
Ins(int &x,int y,bool t)//在最前/最后插入一个节点 { if(!y)return; while(c[x][t])x=c[x][t];
c[x][t]=y,f[y]=x; splay(y,0),x=y; } inline int getr(int x)//找根 { splay(x,0);
while(c[x][0])x=c[x][0]; splay(x,0);return x; } inline void reroot(int
u)//区间平移以换根 { if(getr(u)==u)return; splay(u,0); register int
x=c[u][0];c[u][0]=0,upd(u); Ins(u,x,1); } inline void link(int u,int v,int l) {
register int x=hd[mp[u][v]][l]; intr[mp[u][v]]=intr[mp[v][u]]=1;
u=l*n+u,v=l*n+v; reroot(v),splay(u,0),splay(v,0); se[u]++,se[v]++,upd(v),
Nxt[x]=Nxt[u],Nxt[u]=x,To[x]=v, Nxt[x^1]=Nxt[v],Nxt[v]=x^1,To[x^1]=u;
Ins(v,x,0),Ins(v,x^1,1); gdel[x]=gdel[x^1]=1;
x=c[u][1];while(c[x][0])x=c[x][0]; if(x) { splay(x,u); c[x][0]=v,f[v]=x,upd(x);
} else c[u][1]=v,f[v]=u; upd(u); } inline void cut(int u,int v,int l) {
register int x=hd[mp[u][v]][l]; u=l*n+u,v=l*n+v; reroot(u); splay(x,0);
splay(x^1,x); f[c[x^1][0]]=f[c[x^1][1]]=f[c[x][0]]=0;
splay(u,0),se[u]--,upd(u); Ins(u,c[x^1][1],1); splay(v,0),se[v]--,upd(v); }
inline void pushup(int u,int v,int l,bool t) {
del[hd[mp[u][v]][l]]=del[hd[mp[v][u]][l]]=1; register int x=mp[u][v];
lev[x]=lev[x^1]=l; Gins(u,v,l),Gins(v,u,l); if(t)link(u,v,l); } void dfse(int
x)//向上推一个连通块里所有的树边 { if(!Se[x])return; if(se[x]) { for(int i=Nxt[x];i;i=Nxt[i])
if(!del[i])pushup((x-1)%n+1,(To[i]-1)%n+1,(x-1)/n,1); Nxt[x]=se[x]=0; }
dfse(c[x][0]),dfse(c[x][1]),upd(x); } bool dfst(int x,int y) { if(!St[x])return
0; if(st[x]) { for(int i=nxt[x];i;i=nxt[i]) { if(!(del[i]|gdel[i])) { register
int l=(x-1)/n; if(getr(l*n+to[i])^y)//连到同一个连通块
pushup((x-1)%n+1,(to[i]-1)%n+1,(x-1)/n,0); else { upd(x),x=(x-1)%n+1; for(int
j=0;j<=l;j++) link(x,to[i],j); return 1; } } st[x]--,nxt[x]=nxt[i]; } }
St[x]=0; if(dfst(c[x][0],y))return 1; return dfst(c[x][1],y); } inline bool
rec(int u,int v,int l)//找替代边 { u=l*n+u,v=l*n+v; splay(u,0),splay(v,0);
if(St[u]>St[v])swap(u,v); register int x=getr(v); dfse(u); return dfst(u,x); }
int op,u,v,x,ans; int main() { rd(n),rd(m),gt=n<<4|1; while(m--) {
rd(op),rd(u),rd(v),u^=ans,v^=ans; if(!op) { mp[u][v]=++et,mp[v][u]=++et;
Gins(u,v,0),Gins(v,u,0); if(getr(u)^getr(v))link(u,v,0); } else if(op>1)
getr(u)==getr(v)?puts("Y"),ans=u:(puts("N"),ans=v); else { x=mp[u][v]; for(int
i=0;i<=lev[x];i++) del[hd[x][i]]=del[hd[x^1][i]]=1; if(intr[x]) { for(int
i=lev[x];i>=0;i--) cut(u,v,i); for(int i=lev[x];i>=0;i--) if(rec(u,v,i))break;
} } } }

热门工具换一换