「BZOJ3282」Tree
Description
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
Input
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
Output
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
Sample Input
3 3
1
2
3
1 1 2
0 1 2
0 1 1
Sample Output
3
1
HINT
１＜＝Ｎ，Ｍ＜＝３０００００
题解
lct裸题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define N 300005 using namespace std; int n,m,top; int c[N][2],fa[N],v[N],s[N],q[N]; bool rev[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void update(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[x]^=1;rev[l]^=1;rev[r]^=1; swap(c[x][0],c[x][1]); } } bool isroot(int x) { return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void rotate(int x) { int y=fa[x],z=fa[y],l,r; 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; update(y);update(x); } void splay(int x) { top=0;q[++top]=x; for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i]; for(int i=top;i;i--) pushdown(q[i]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) { if(c[y][0]==x^c[z][0]==y)rotate(x); else rotate(y); } rotate(x); } } void access(int x) { for(int t=0;x;t=x,x=fa[x]) splay(x),c[x][1]=t,update(x); } void makeroot(int x) { access(x);splay(x);rev[x]^=1; } int find(int x) { access(x);splay(x); while(c[x][0])x=c[x][0]; return x; } void cut(int x,int y) { makeroot(x);access(y);splay(y); if(c[y][0]==x)c[y][0]=fa[x]=0; } void link(int x,int y) { makeroot(x);fa[x]=y; } int main() { n=read();m=read(); for(int i=1;i<=n;i++)v[i]=read(),s[i]=v[i]; int opt,x,y; for(int i=1;i<=m;i++) { opt=read();x=read();y=read(); switch(opt) { case 0:makeroot(x);access(y);splay(y);printf("%d\n",s[y]);break; case 1:if(find(x)!=find(y))link(x,y);break; case 2:if(find(x)==find(y))cut(x,y);break; case 3:access(x);splay(x);v[x]=y;update(x);break; } } return 0; } |
计数器 9787656
OI 课件=>
OI 课件=>
bzoj上好像找不到题目了。。
变权限题了