【bzoj2049】【SDOI2008】【洞穴勘测】【lct】
发布日期:2021-11-16 15:38:17 浏览次数:24 分类:技术文章

本文共 2889 字,大约阅读时间需要 9 分钟。

Description

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

Input

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

Output

对每个Query指令,输出洞穴u和洞穴v是否互相连通:是输出”Yes”,否则输出”No”。(不含双引号)

Sample Input

样例输入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



Sample Output

样例输出1 cave.out
No
Yes
No


样例输出2 cave.out

Yes
No

HINT

数据说明 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指令将摧毁的是一条存在的通道本题输入、输出规模比较大,建议c\c++选手使用scanf和printf进行I\O操作以免超时

题解:这算是最简单的lct了吧。

代码:

#include
#include
#include
#define N 10005using namespace std;int m,fa[N],c[N][2],n,x,y,st[N];bool re[N];char ch[10];bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}void rotata(int x){ int y=fa[x],z=fa[y],l,r; if (c[y][0]==x)l=0;else l=1;r=l^1; if (!isroot(y)){if (c[z][0]==y) c[z][0]=x;else c[z][1]=x;} fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y;}void pushdown(int x){ int l=c[x][0],r=c[x][1]; if(re[x]){ re[l]^=1;re[r]^=1;re[x]^=1; swap(c[x][0],c[x][1]); } }void splay(int x){ int top(0);st[++top]=x; for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; for (int i=top;i;i--) pushdown(st[i]); while (!isroot(x)){ int y=fa[x],z=fa[y]; if (!isroot(y)){ if (c[y][0]==x^c[z][0]==y) rotata(x); else rotata(y); } rotata(x); } }void access(int x){ int t(0); while (x){splay(x);c[x][1]=t;t=x;x=fa[x];} }void rever(int x){access(x);splay(x);re[x]^=1;}void link(int x,int y){rever(x);fa[x]=y;}void cut(int x,int y){rever(x);access(y);splay(y);c[y][0]=fa[x]=0;}int find(int x){ access(x);splay(x); int y=x; while (c[y][0]) y=c[y][0]; return y; }int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ scanf("%s",ch);scanf("%d%d",&x,&y); if (ch[0]=='C') link(x,y); if (ch[0]=='D') cut(x,y); if (ch[0]=='Q'){ if (find(x)==find(y)) printf("Yes\n"); else printf("No\n"); } } }

转载地址:https://blog.csdn.net/sunshinezff/article/details/50969959 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj2631】【tree】【lct】
下一篇:【bzoj3437】【小p的牧场】【斜率优化dp】

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月06日 01时04分05秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python mod,mod_python的安装 2019-04-21
python分析彩票数据,这波太炸了!Python脚本可视化居然可以这么玩 2019-04-21
简单的mysql重置root密码,重置mysql的root密码最简单的方法 2019-04-21
用matlab仿真mmc环流抑制器,一种基于准PR控制原理的MMC阀组环流抑制方法 2019-04-21
oracle 排序的分析函数,Oracle SQL:使用分析排序函数 2019-04-21
oracle direct for hdfs xi下载,ORACLE连接HDFS有个专项的解决方案 2019-04-21
java 403怎么抛出_java – 如何在Spring MVC中返回403禁止? 2019-04-21
java jsch工具类_Java工具集-JSch连接远程服务器工具类 2019-04-21
cmd背景变红1003无标题_怎样修改cmd中文字的大小、颜色和背景颜色呢 原来是这样的... 2019-04-21
php rand() 重复,php – mt_rand()给我总是相同的数字 2019-04-21
php taglib.php,thinkphp5 taglib自定义标签教程 2019-04-21
java常用包类 array,Java中的StringBuffer和数组Arrays以及常用类型的包装类 2019-04-21
ctf常见php,CTF中常见的PHP伪协议 2019-04-21
php语言冒泡法,PHP 冒泡排序法 2019-04-21
php如何数组去重复,PHP如何去除数组重复元素? 2019-04-21
java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 2019-04-21
ui php h5,画出自己的UI组件的详情 2019-04-21
linux服务文件编写,linux编写systemd下服务脚本 2019-04-21
hdfs linux 目录是否存在,Linux中判断hdfs文件是否存在 2019-04-21
linux学习需要什么基础,学linux需要什么基础? 2019-04-21