【bzoj3282】【Tree】【lct】
发布日期:2021-11-16 15:38:19 浏览次数:14 分类:技术文章

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

Description

给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。

0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。

2:后接两个整数(x,y),代表删除边(x,y),保证边(x,y)存在。

3:后接两个整数(x,y),代表将点X上的权值变成Y。

 

Input

第1行两个整数,分别为N和M,代表点数和操作数。

第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。

第N+2行到第N+M+1行,每行三个整数,分别代表操作类型和操作所需的量。

 

Output

对于每一个0号操作,你须输出X到Y的路径上点权的Xor和。

Sample Input

3 3
1
2
3
1 1 2
0 1 2
0 1 1

Sample Output

3
1

HINT

1<=N,M<=300000

题解:对于不合法的删边,在cut的时候判断一下两个点是否连在一起即可。

代码:

#include
#include
#include
#define N 300010using namespace std;int c[N][2],k,x,y,fa[N],rev[N],s[N],v[N],st[N],n,m;bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}void updata(int x){ int l=c[x][0],r=c[x][1]; s[x]=s[l]^s[r]^v[x];}void pushdown(int x){ int l=c[x][0],r=c[x][1]; if (rev[x]){ rev[l]^=1;rev[r]^=1;rev[x]^=1; swap(c[x][0],c[x][1]); }}void rotata(int x){ int l,r,y=fa[x],z=fa[y]; 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; updata(y);updata(x);}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(y); rotata(x); } rotata(x); }}void access(int x){int t(0);while(x){splay(x);c[x][1]=t;t=x;updata(x);x=fa[x];}} void makeroot(int x){access(x);splay(x);rev[x]^=1;}void split(int x,int y){makeroot(y);access(x);splay(x);} void link(int x,int y){makeroot(x);fa[x]=y;}void cut(int x,int y){makeroot(x);access(y);splay(y);if(c[y][0]==x)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<=n;i++){scanf("%d",&v[i]);s[i]=v[i];} for (int i=1;i<=m;i++){ scanf("%d%d%d",&k,&x,&y); if (k==0){split(x,y);printf("%d\n",s[x]);} if (k==1) if (find(x)!=find(y)) link(x,y); if (k==2) if (find(x)==find(y)) cut(x,y); if (k==3){makeroot(x);v[x]=y;updata(x);} } }

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

上一篇:【bzoj2594】【WC2006】【水管局长加强版】【lct】
下一篇:【bzoj1180】【CROATIAN2009】【OTOCI】【lct】

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月18日 02时40分51秒

关于作者

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

推荐文章

php charat,如何在PHP中生成字符串的所有排列? 2019-04-21
php rabbitmq yii2,PHP rabbitmq producer for yii2 2019-04-21
php选择什么框架,关于如何正确使用PHP框架及如何选择框架之我见 2019-04-21
matlab删除矩阵某些数据库,matlab中如何删除矩阵中特定的几个元素 2019-04-21
matlab radon变换代码,求matlab中radon变换具体的实现代码 2019-04-21
php artisan nohup,artisan命令生成和redis消息订阅和任务调度 2019-04-21
java怎么设置按钮凹凸状态,FragmentTabHost实现中间按钮凸出效果 2019-04-21
python读取excel多个sheet_解决python pandas读取excel中多个不同sheet表格存在的问题 2019-04-21
苹果终端date命令_mac date命令 2019-04-21
is属性用法 vue_vue组件讲解(is属性的用法)模板标签替换操作 2019-04-21
webpack 读取文件夹下的文件_webpack打包某个文件夹下的所有js 2019-04-21
datepick二格式 化时间_Date日期格式转换 2019-04-21
华为的鸿蒙系统可以装在电脑上吗_鸿蒙2.0手机快了,华为EMUI 11透露关键信息... 2019-04-21
python大型工程文件架构_聊聊Python模块导入机制与大型项目规范 2019-04-21
oracle java long_利用oracle long类型字段,插入大文本 2019-04-21
java jar jvm_java jvm揭幕——高级开发 2019-04-21
java class .method_在Java中,this.method()和method()之间有什么区别? 2019-04-21
java state machine_State Machine Compiler--教程第一部分 2019-04-21
java io有哪些实现类_广州Java面试宝典之Java IO篇 2019-04-21
java中进程和线程的区别和联系_进程和线程有什么联系和区别? 2019-04-21