【BZOJ】【3282】Tree

时间:2021-12-04 11:20:51

LCT

  喜闻乐见的Link-Cut-Tree……

  srO zyf

  http://www.cnblogs.com/zyfzyf/p/4149109.html

  目测我是第222个?………………不要在意这些细节……

  

  和以前写的splay还是有些区别呢……

  比如splay中Push_down的写法……还有rotate的新姿势~

  算法看看论文什么的……很好懂

 /**************************************************************
Problem: 3282
User: Tunix
Language: C++
Result: Accepted
Time:2596 ms
Memory:8596 kb
****************************************************************/ //BZOJ 3282
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
const int N=;
#define debug int c[N][],fa[N],v[N],s[N],st[N],top=;
bool rev[N];
int n,m; void Push_up(int x){
int l=c[x][],r=c[x][];
s[x]=s[l]^s[r]^v[x];
}
void Push_down(int x){
int l=c[x][],r=c[x][];
if(rev[x]){
rev[x]^=; rev[l]^=; rev[r]^=;
swap(c[x][],c[x][]);
}
}
bool isroot(int x){
return c[fa[x]][]!=x && c[fa[x]][]!=x;
}
void rotate(int x){
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if (!isroot(y)) c[z][c[z][]==y]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
Push_up(y); Push_up(x);
}
void splay(int x){
top=; st[top++]=x;
for(int i=x;!isroot(i);i=fa[i])
st[top++]=fa[i];
while(top--) Push_down(st[top]); while(!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (c[y][]==x^c[z][]==y) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
for(int t=;x;t=x,x=fa[x])
splay(x),c[x][]=t,Push_up(x);
}
void makeroot(int x){
access(x); splay(x); rev[x]^=;
}
int find(int x){
access(x); splay(x);
while(c[x][]) x=c[x][];
return x;
}
void cut(int x,int y){
makeroot(x); access(y); splay(y);
if (c[y][]==x) c[y][]=fa[x]=;
}
void link(int x,int y){
makeroot(x); fa[x]=y;
}
//LCT end
int main(){
#ifndef ONLINE_JUDGE
freopen("file.in","r",stdin);
// freopen("file.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
F(i,,n) {scanf("%d",&v[i]); s[i]=v[i];} int c,x,y;
F(i,,m){
scanf("%d%d%d",&c,&x,&y);
switch(c){
case :makeroot(x); access(y); splay(y); printf("%d\n",s[y]);break;
case :if (find(x)!=find(y)) link(x,y);break;
case :if (find(x)==find(y)) cut(x,y);break;
case :access(x); splay(x); v[x]=y; Push_up(x);break;
}
}
return ;
}

3282: Tree

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 829  Solved: 342
[Submit][Status][Discuss]

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

Source

[Submit][Status][Discuss]

【BZOJ】【3282】Tree的更多相关文章

  1. 【Bzoj 1835 基站选址】

    基站选址的区间里隐藏着DP优化的机密…… 分析:       不论是做过乘积最大还是石子合并,或者是其他的入门级别的区间DP题目的人呐,大米并认为读题后就能够轻松得出一个简洁明了的Dp转移方程.    ...

  2. 【BZOJ 2744 朋友圈】

    Time Limit: 30 Sec  Memory Limit: 128 MBSubmit: 1570  Solved: 532[Submit][Status][Discuss] Descripti ...

  3. 【BZOJ 5038 不打兔子】

    Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 22  Solved: 8[Submit][Status][Discuss] Description 勤 ...

  4. 【BZOJ 1088 扫雷Mine】模拟

    http://www.lydsy.com/JudgeOnline/problem.php?id=1088 2*N的扫雷棋盘,第二列的值a[i]记录第 i 个格子和它8连通的格子里面雷的数目. 第一列的 ...

  5. 【BZOJ做题记录】07&period;07~?

    在NOI一周前重开一个坑 最后更新时间:7.08 07:38 7.06 下午做的几道CQOI题: BZOJ1257: [CQOI2007]余数之和sum:把k mod i写成k-k/i*i然后分段求后 ...

  6. 【bzoj5050】【bzoj九月月赛H】建造摩天楼

    讲个笑话,这个题很休闲的. 大概是这样的,昨天看到这个题,第一眼星际把题目看反了然后感觉这是个傻逼题. 后来发现不对,这个修改一次的影响是很多的,可能导致一个数突然可以被改,也可能导致一个数不能被改. ...

  7. 【BZOJ 4151 The Cave】

    Time Limit: 5 Sec  Memory Limit: 256 MBSec  Special JudgeSubmit: 293  Solved: 144[Submit][Status][Di ...

  8. 【BZOJ 2458 最小三角形】

    Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1551  Solved: 549[Submit][Status][Discuss] Descripti ...

  9. 【BZOJ 5000 OI树】

    Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 107  Solved: 64[Submit][Status][Discuss] Description ...

  10. 【BZOJ 5047 空间传送装置】

    Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 282  Solved: 121[Submit][Status][Discuss] Descriptio ...

随机推荐

  1. 安装ANDROID5&period;0 ,adb连接不上

    一.ADB PC端需要换成5.0 的版本 二.是4.3默认端口5555,但是现在没有连接上.即绑定端口. setprop service.adb.tcp.port 5555 stop adbd sta ...

  2. 根据BIOS信息修改主机名

    Dell: Rename-Computer -NewName ("CNHZPD-" + (Get-WmiObject -class win32_Bios).SerialNumber ...

  3. CSS规范之BFC &amp&semi; IFC

    元素是文档结构的基础,在CSS中,每个元素生成了一个包含了元素内容的框(box,也译为"盒子").但是不同的元素显示的方式会有所不同,例如<div>和<span& ...

  4. java基础篇-jar打包

    以helloworld程序为例: 一:正常流程: 1.首先编写一个hello.java的程序: public class Hello { public static void main(String[ ...

  5. Asp&period;Net WebAPI Get提交、Post提交处理

    1.启用跨域提交 <system.webServer> <httpProtocol> <customHeaders> <add name="Acce ...

  6. codeforces 887A Div&period; 64 思维 模拟

    A. Div. 64 time limit per test 1 second memory limit per test 256 megabytes input standard input out ...

  7. nginx1&period;14&period;0日志打印

    nginx日志打印 http属性log_format来设置日志格式 ,参考 https://www.jb51.net/article/52573.htm  <nginx日志配置指令详解> ...

  8. Spring 获取bean 几种方式

    转载自: http://www.cnblogs.com/luoluoshidafu/p/5659574.html 1.读取xml文件的方式,这种在初学入门的时候比较适用 . ApplicationCo ...

  9. celery 应用

    开启服务 #日志 级别 celery -A write_file worker -l info file name :write_file.pyfrom celery import Celery ce ...

  10. 【Java多线程】Executor框架的详解

    在Java中,使用线程来异步执行任务.Java线程的创建与销毁需要一定的开销,如果我们为每一个任务创建一个新线程来执行,这些线程的创建与销毁将消耗大量的计算资源.同时,为每一个任务创建一个新线程来执行 ...