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\)行\(2\)个整数\(N,M\),代表点数和操作数.
第\(2\)行到第\(N+1\)行,每行\(1\)个整数,整数\(\in[1,10^9]\),代表每个点的权值.
第\(N+2\)行到第\(N+M+1\)行,每行\(3\)个整数,分别代表操作类型和操作所需的量.
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\leq{N,M}\leq300000\).
Solution
\(LCT\)裸题,\(Splay\)维护\(xor\)和.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 300010
using namespace std;
typedef long long ll;
struct Splay{
int c[2],f,sum,rev;//树边方向
}tr[N];//大小看深度,维护实路径,最左/右端点对应路径头/尾
int w[N],n,m;
stack<int> s;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline bool son(int u){
return tr[tr[u].f].c[1]==u;
}
inline void ins_p(int f,int u,int c){
tr[f].c[c]=u;tr[u].f=f;
}
inline void recnt(int u){
tr[u].sum=w[u]^tr[tr[u].c[0]].sum^tr[tr[u].c[1]].sum;
}
inline bool isroot(int u){
return tr[tr[u].f].c[0]!=u&&tr[tr[u].f].c[1]!=u;
}
inline void rotate(int u){
int f=tr[u].f;bool c=son(u);
if(isroot(f)) tr[u].f=tr[f].f;
else ins_p(tr[f].f,u,son(f));
ins_p(f,tr[u].c[c^1],c);
ins_p(u,f,c^1);
recnt(f);recnt(u);
}
inline void down(int u){
if(tr[u].rev){
tr[u].rev=0;
swap(tr[u].c[0],tr[u].c[1]);
tr[tr[u].c[0]].rev^=1;
tr[tr[u].c[1]].rev^=1;
}
}
inline void splay(int u){
s.push(u);
for(int v=u;!isroot(v);v=tr[v].f) s.push(tr[v].f);
while(!s.empty()){
down(s.top());s.pop();
}
while(!isroot(u)){
if(isroot(tr[u].f)) rotate(u);
else if(son(tr[u].f)==son(u)){
rotate(tr[u].f);rotate(u);
}
else{
rotate(u);rotate(u);
}
}
}
inline void access(int u){
for(int lst=0;u;lst=u,u=tr[u].f){
splay(u);tr[u].c[1]=lst;recnt(u);
if(lst) tr[lst].f=u;
}
}
//使u成为所在树的根节点
inline void makeroot(int u){
access(u);splay(u);tr[u].rev^=1;
}
//找到u所在树的根节点
inline int findroot(int u){
access(u);splay(u);
while(down(u),tr[u].c[0]) u=tr[u].c[0];
splay(u);
return u;
}
//u,v同一平衡树,u为v的左孩子
inline void select(int u,int v){
makeroot(u);access(v);splay(v);
}
inline void link(int u,int v){
makeroot(u);tr[u].f=v;
}
inline void cut(int u,int v){
select(u,v);tr[v].c[0]=tr[u].f=0;recnt(v);
}
inline void change(int u,int k){
makeroot(u);w[u]=k;recnt(u);
}
inline void Aireen(){
n=read();m=read();
for(int i=1;i<=n;++i) tr[i].sum=w[i]=read();
int ty,x,y;
while(m--){
ty=read();x=read();y=read();
switch(ty){
case 0:select(x,y);printf("%d\n",tr[y].sum);break;
case 1:if(findroot(x)!=findroot(y)) link(x,y);break;
case 2:if(findroot(x)==findroot(y)) cut(x,y);break;
case 3:change(x,y);break;
}
}
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
2017-04-06 21:50:07