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
1
2
3
1 1 2
0 1 2
0 1 1
Sample Output
1
HINT
1<=N,M<=300000
Source
【BZOJ】【3282】Tree的更多相关文章
-
【Bzoj 1835 基站选址】
基站选址的区间里隐藏着DP优化的机密…… 分析: 不论是做过乘积最大还是石子合并,或者是其他的入门级别的区间DP题目的人呐,大米并认为读题后就能够轻松得出一个简洁明了的Dp转移方程. ...
-
【BZOJ 2744 朋友圈】
Time Limit: 30 Sec Memory Limit: 128 MBSubmit: 1570 Solved: 532[Submit][Status][Discuss] Descripti ...
-
【BZOJ 5038 不打兔子】
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 22 Solved: 8[Submit][Status][Discuss] Description 勤 ...
-
【BZOJ 1088 扫雷Mine】模拟
http://www.lydsy.com/JudgeOnline/problem.php?id=1088 2*N的扫雷棋盘,第二列的值a[i]记录第 i 个格子和它8连通的格子里面雷的数目. 第一列的 ...
-
【BZOJ做题记录】07.07~?
在NOI一周前重开一个坑 最后更新时间:7.08 07:38 7.06 下午做的几道CQOI题: BZOJ1257: [CQOI2007]余数之和sum:把k mod i写成k-k/i*i然后分段求后 ...
-
【bzoj5050】【bzoj九月月赛H】建造摩天楼
讲个笑话,这个题很休闲的. 大概是这样的,昨天看到这个题,第一眼星际把题目看反了然后感觉这是个傻逼题. 后来发现不对,这个修改一次的影响是很多的,可能导致一个数突然可以被改,也可能导致一个数不能被改. ...
-
【BZOJ 4151 The Cave】
Time Limit: 5 Sec Memory Limit: 256 MBSec Special JudgeSubmit: 293 Solved: 144[Submit][Status][Di ...
-
【BZOJ 2458 最小三角形】
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1551 Solved: 549[Submit][Status][Discuss] Descripti ...
-
【BZOJ 5000 OI树】
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 107 Solved: 64[Submit][Status][Discuss] Description ...
-
【BZOJ 5047 空间传送装置】
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 282 Solved: 121[Submit][Status][Discuss] Descriptio ...
随机推荐
-
安装ANDROID5.0 ,adb连接不上
一.ADB PC端需要换成5.0 的版本 二.是4.3默认端口5555,但是现在没有连接上.即绑定端口. setprop service.adb.tcp.port 5555 stop adbd sta ...
-
根据BIOS信息修改主机名
Dell: Rename-Computer -NewName ("CNHZPD-" + (Get-WmiObject -class win32_Bios).SerialNumber ...
-
CSS规范之BFC &; IFC
元素是文档结构的基础,在CSS中,每个元素生成了一个包含了元素内容的框(box,也译为"盒子").但是不同的元素显示的方式会有所不同,例如<div>和<span& ...
-
java基础篇-jar打包
以helloworld程序为例: 一:正常流程: 1.首先编写一个hello.java的程序: public class Hello { public static void main(String[ ...
-
Asp.Net WebAPI Get提交、Post提交处理
1.启用跨域提交 <system.webServer> <httpProtocol> <customHeaders> <add name="Acce ...
-
codeforces 887A Div. 64 思维 模拟
A. Div. 64 time limit per test 1 second memory limit per test 256 megabytes input standard input out ...
-
nginx1.14.0日志打印
nginx日志打印 http属性log_format来设置日志格式 ,参考 https://www.jb51.net/article/52573.htm <nginx日志配置指令详解> ...
-
Spring 获取bean 几种方式
转载自: http://www.cnblogs.com/luoluoshidafu/p/5659574.html 1.读取xml文件的方式,这种在初学入门的时候比较适用 . ApplicationCo ...
-
celery 应用
开启服务 #日志 级别 celery -A write_file worker -l info file name :write_file.pyfrom celery import Celery ce ...
-
【Java多线程】Executor框架的详解
在Java中,使用线程来异步执行任务.Java线程的创建与销毁需要一定的开销,如果我们为每一个任务创建一个新线程来执行,这些线程的创建与销毁将消耗大量的计算资源.同时,为每一个任务创建一个新线程来执行 ...