【BZOJ3282】Tree (Link-Cut Tree)

题面

BZOJ权限题呀,良心luogu上有

题解

Link-Cut Tree班子提

最近因为NOIP考炸了

学科也炸了

时间显然没有

以后再来填LCT的坑

这种题目直接上代码了。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 333333
#define ls (t[x].ch[0])
#define rs (t[x].ch[1])
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Node
{
int ch[2],ff;
int rev,v,s;
}t[MAX];
int n,m;
bool isroot(int x){return t[t[x].ff].ch[0]!=x&&t[t[x].ff].ch[1]!=x;}
void pushup(int x){t[x].s=t[ls].s^t[rs].s^t[x].v;}
void rotate(int x)
{
int y=t[x].ff,z=t[y].ff;
int k=t[y].ch[1]==x;
if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;
t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;
t[x].ch[k^1]=y;t[y].ff=x;
pushup(y);pushup(x);
}
void pushdown(int x)
{
if(!t[x].rev)return;
t[x].rev^=1;swap(ls,rs);
if(ls)t[ls].rev^=1;if(rs)t[rs].rev^=1;
}
int S[MAX],top;
void Splay(int x)
{
S[top=1]=x;
for(int i=x;!isroot(i);i=t[i].ff)S[++top]=t[i].ff;
while(top)pushdown(S[top--]);
while(!isroot(x))
{
int y=t[x].ff,z=t[y].ff;
if(!isroot(y))
(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x){for(int y=0;x;y=x,x=t[x].ff)Splay(x),rs=y,pushup(x);}
void makeroot(int x){access(x);Splay(x);t[x].rev^=1;}
void split(int x,int y){makeroot(x);access(y);Splay(y);}
void link(int x,int y){makeroot(x);t[x].ff=y;}
void cut(int x,int y){split(x,y);if(t[y].ch[0]==x)t[y].ch[0]=t[x].ff=0;}
int findroot(int x){access(x);Splay(x);while(ls)x=ls;return x;}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)t[i].v=read();
while(m--)
{
int opt=read(),x=read(),y=read();
if(opt==0){split(x,y);printf("%d\n",t[y].s);}
if(opt==1)if(findroot(x)!=findroot(y))link(x,y);
if(opt==2)cut(x,y);
if(opt==3)makeroot(x),t[x].v=y,pushup(x);
}
}

最新文章

  1. Visual Studio的背景插件
  2. Ubuntu 14.04(amd64)安装Oracle11g XE(x64)
  3. 使用 Arduino 和 LM35 温度传感器监测温度
  4. ubuntu16.04连接android手机蓝牙共享网络热点
  5. Java中的JDK动态代理
  6. Python脚本模拟登录网页之ZiMuZu篇
  7. linux压缩解压
  8. Google Code Pretiffy 代码 着色 高亮 开源 javascript(JS)库
  9. java小算法—大衍数列
  10. ECS活动真实IP (前端存在SLB)
  11. python自动化测试应用-番外篇--接口测试2
  12. CSS背景和CSS列表
  13. NOIP2013题解
  14. Ubuntu 16.04下添加新用户
  15. ELK (Elasticsearch+Logstash+Kibana)部署
  16. ubuntu18安装ubuntu kylin软件中心
  17. 网易云首席安全架构师谈安全新形势:DDOS两三天,游戏玩家数从几万降到几百
  18. go语言基础之数组做函数参数是值拷贝
  19. mongodb3 设置用户名密码 ,linux
  20. package分析

热门文章

  1. 个人Win10 +archlinux安装笔记
  2. FireMonkey 导出目前 Style 另存文件
  3. 学习下nginx负载均衡--深入理解nginx
  4. mount --bind 重启后失效的解决办法
  5. sql学习笔记--存储过程
  6. ABP的事件总线和领域事件(EventBus &amp; Domain Events)
  7. 浅析LruCache原理
  8. Java中单元测试中:@BeforeClass,@Before,@Test,@After,@AfterClass中的问题详解
  9. magic_quotes_gpc(魔术引号开关)
  10. 【转】hibernate.hbm.xml详解
  11. Spring中实现定时调度
  12. NodeJS之微信开发
  13. JAVA RPC (六) 之手把手从零教你写一个生产级RPC之client的代理
  14. Call to undefined function Workerman\posix_getpid()
  15. python生成随机整数
  16. CSS3 过渡动画
  17. 从零开始学Kotlin-枚举(9)
  18. 翻译:GLSL的顶点位移贴图
  19. Visual Studio 设置C#语言代码格式
  20. HttpServletRequest继承字ServletRequest的常用方法