2049: [Sdoi2008]Cave 洞穴勘测 - #include <Seter> - using namespace Orz;

2049: [Sdoi2008]Cave 洞穴勘测

Seter posted @ 2011年9月12日 14:52 in BZOJ with tags DTP DisjointSet SDOI LCT , 4615 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2049

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
150942	Seter	2049	Accepted	792 kb	596 ms	C/Edit	723 B	2011-09-12 13:42:35

这题莫名其妙R1了……掉RP啊……

这题是维护一个动态森林……乍看是动态树其实真的是动态树……不过这题只要暴力就可以了！难道数据是随机的么？

其实这东西就是一个并查集……但是没有路径压缩（能否按秩合并？）……否则就很难destory了。

Cxy操作：x提根然后将x的父亲设为y。

Dxy操作：x提根，此时y的父亲必为x，所以将y的父亲清空即可。

Qxy操作：x提根，暴力查找y的根是不是x。

如何提根？很简单。把x到根的顺序颠倒过来就可以了。即原来a是b的父亲，让b成为a的父亲。

2049
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24	`#include <stdio.h>` `#include <string.h>` `int` `n,m,f[10000];` `inline` `getint(){` `int` `re=0,ch=getchar(),k;` `while(ch!='-'&&(ch<'0'\|\|ch>'9'))if((ch=getchar())<=0)return` `-1;` `for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;` `return` `k?-re:re;` `}inline` `void` `SetRoot(x){` `int` `y,t=f[x];` `for(f[x]=-1;(y=t)!=-1;x=y){t=f[y];f[y]=x;}` `}main(){` `int` `ch,x;n=getint();` `memset(f,-1,sizeof(f));` `for(m=getint();m--&&(ch=getchar())>0;){` `SetRoot(x=getint()-1);` `if(ch=='C')f[x]=getint()-1;` `else` `if(ch=='D')f[getint()-1]=-1;` `else{` `for(ch=getint()-1;ch!=-1&&ch!=x;ch=f[ch]);` `puts(ch==x?"Yes":"No");` `}` `}return` `0;` `}`

用LCT写了下，结果调了5个小时，今天睡觉的时候想到貌似少了个pushdown，结果真的少了个pushdown……

每个操作的执行方法挺多的，我的不是最优的……

首先让Access操作（简称A操作）返回最后一次接上去的时候的父亲，这样A(x)后A(y)返回的就是LCA了。

Q：A(x)后如果A(y)返回x，那么说明LCA是x，显然Yes；否则如果将xSplay到顶后有父亲，说明A(y)时被断掉了，也是Yes；否则No。

D：A(x)后A(y)返回的就是父亲，A(父亲)后splay儿子并将其根设为空

C：最麻烦的操作，为了将x旋到根，A(x)后splay(x)，然后给x打上翻转标记……然后x就是根了（你可以想想为什么），将x的父亲设为y即可。

为了处理翻转标记，一定要弄清楚pushdown的顺序……一开始我在splay里pushdown，但是处理完x再处理fx的话，x可能又上了标记！所以5个小时犯二后我在rot操作里按照ffx,fx,x的顺序pushdown了，TLE->AC……

2049lct
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51	`#include <stdio.h>` `#define maxn 10000` `typedef` `struct` `_Splay{struct` `_Splay c[2],f;_Bool r;}Splay,PSplay;` `Splay null,st[maxn];` `inline` `PSplay fa(PSplay x){return` `x->f->c[0]==x\|\|x->f->c[1]==x?x->f:&null;}` `inline` `PSplay tran(PSplay x){PSplay t;if(x->r)x->r=0,(t=x->c[0])->r^=1,(x->c[0]=x->c[1])->r^=1,x->c[1]=t;return` `x;}` `inline` `PSplay node(PSplay x){x->f=x->c[0]=x->c[1]=&null;return` `x;}` `inline` `PSplay rot(PSplay x){` `PSplay fx=fa(x),ffx=tran(fa(fx));` `_Bool c=tran(fx)->c[1]==x,fc=ffx->c[1]==fx;tran(x);` `if(fx!=&null){` `x->f=fx->f;` `if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;` `if(ffx!=&null)ffx->c[fc]=x;` `(fx->f=x)->c[!c]=fx;` `}return` `x;` `}inline` `PSplay splay(PSplay x,PSplay p){` `PSplay fx,ffx;if(x==&null)return` `x;` `for(;(fx=fa(x))!=p;rot(x))if((ffx=fa(fx))!=p)rot((ffx->c[1]==fx)==(fx->c[1]==x)?fx:x);` `return` `tran(x);` `}inline` `getint(){` `int` `re=0,ch=getchar();_Bool k;` `while(ch!='-'&&(ch<'0'\|\|ch>'9'))if((ch=getchar())<=0)return` `-1;` `for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re10+ch-48;` `return` `k?-re:re;` `}inline` `PSplay Access(PSplay x){` `PSplay t=&null;` `while(splay(x,&null)->c[1]=t,(x=(t=x)->f)!=&null);` `return` `splay(t,&null);` `}main(){` `int` `n,i=-1,x,y;` `null.f=null.c[0]=null.c[1]=&null;` `for(n=getint();++i!=n;node(st+i));` `for(n=getint();n--;){` `while((i=getchar())!='Q'&&i!='D'&&i!='C');` `if(i=='Q'){` `Access(st+(x=getint()-1));` `puts(Access(st+(y=getint()-1))!=st+x&&splay(st+x,&null)->f==&null?"No":"Yes");` `}else` `if(i=='D'){` `Access(st+(x=getint()-1));` `if(Access(st+(y=getint()-1))==st+x){` `Access(st+x);` `splay(st+y,&null)->f=&null;` `}else` `splay(st+x,&null)->f=&null;` `}else{` `Access(st+(x=getint()-1));` `splay(st+x,&null)->r^=1;` `st[x].f=splay(st+getint()-1,&null);` `}` `}return` `0;` `}`