BZOJ2049 [SDOI2008]Cave 洞穴勘测

【问题描述】

辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

【输入格式】

第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

【输出格式】

对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

【输入样例】

样例输入1 cave.in
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127
样例输入2 cave.in

3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3

【输出样例】

样例输出1 cave.out
No
Yes
No

样例输出2 cave.out

Yes
No

【数据规模】

数据说明 10%的数据满足n≤1000, m≤20000 20%的数据满足n≤2000, m≤40000 30%的数据满足n≤3000, m≤60000 40%的数据满足n≤4000, m≤80000 50%的数据满足n≤5000, m≤100000 60%的数据满足n≤6000, m≤120000 70%的数据满足n≤7000, m≤140000 80%的数据满足n≤8000, m≤160000 90%的数据满足n≤9000, m≤180000 100%的数据满足n≤10000, m≤200000 保证所有Destroy指令将摧毁的是一条存在的通道本题输入、输出规模比较大，建议cc++选手使用scanf和printf进行IO操作以免超时

正解：link cut tree

结题报告：一上午终于学会了LCT，打到板子题练练手

  1 #include <iostream>
  2 #include <iomanip>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <string>
  9 #define RG register
 10 const int N = 20000;
 11 
 12 using namespace std;
 13 
 14 int gi(){
 15     char ch=getchar();int x=0;
 16     while(ch<'0' || ch>'9') ch=getchar();
 17     while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
 18     return x;
 19 }
 20 
 21 int st[N],c[N][2],fa[N],rev[N];
 22 char ch[10];
 23 
 24 int isroot(int x){
 25     return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
 26 }
 27 
 28 void pushdown(int x){
 29     if (rev[x]==0) return;
 30     RG int l=c[x][0],r=c[x][1];
 31     rev[x]^=1,rev[l]^=1,rev[r]^=1;
 32     swap(c[x][0],c[x][1]);
 33     return;
 34 }
 35 
 36 void rotate(int x){
 37     RG int l,r,y=fa[x],z=fa[y];
 38     if (c[y][0]==x) l=0;
 39     else l=1;r=l^1;
 40     if (!isroot(y))
 41         if (c[z][0]==y) c[z][0]=x;
 42         else c[z][1]=x;
 43     fa[x]=z,fa[y]=x,fa[c[x][r]]=y;
 44     c[y][l]=c[x][r],c[x][r]=y;
 45     return;
 46 }
 47 
 48 void splay(int x){
 49     int tot=0;
 50     st[++tot]=x;
 51     for (RG int i=x; !isroot(i); i=fa[i]) st[++tot]=fa[i];
 52     for (RG int i=tot; i; --i) pushdown(st[i]);
 53     while(!isroot(x)){
 54         RG int y=fa[x],z=fa[y];
 55         if (!isroot(y))
 56             if (c[y][0]==x ^ c[z][0]==y) rotate(x);
 57             else rotate(y);
 58         rotate(x);
 59     }
 60     return;
 61 }
 62 
 63 void access(int x){
 64     int t=0;
 65     while(x){
 66         splay(x);
 67         c[x][1]=t;
 68         t=x,x=fa[x];
 69     }
 70     return;
 71 }
 72 
 73 void rever(int x){
 74     access(x),splay(x),rev[x]^=1;
 75     return;
 76 }
 77 
 78 void link(int x,int y){
 79     rever(x),fa[x]=y;
 80     return;
 81 }
 82 
 83 void cut(int x,int y){
 84     rever(x),access(y),splay(y),c[y][0]=fa[x]=0;
 85     return;
 86 }
 87 
 88 int find(int x){
 89     access(x),splay(x);
 90     while(c[x][0]) x=c[x][0];
 91     return x;
 92 }
 93 
 94 int main(){
 95     RG int n=gi(),m=gi();
 96     for (RG int i=1; i<=m; ++i){
 97         scanf("%s",ch);
 98         RG int x=gi(),y=gi();
 99         if (ch[0]=='C') link(x,y);
100         else if (ch[0]=='D') cut(x,y);
101         else
102             if (find(x)==find(y)) printf("Yes
");
103             else printf("No
");
104     }
105 }