【模板】动态树

Source and Judge

Luogu3690

Problem

【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和。
【Limited conditions】
单词数n<=60
所有字符串长度、m<=100
【Sample input】
3 3
1
2
3
1 1 2
0 1 2
0 1 1
【Sample output】
3
1

【Sample explanation】

Record

1h

Analysis

请先思考后再展开

省选前模板练手

Code

请先思考后再展开
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll mymax(ll x,ll y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(ll &x,ll y) {if(x<y) x=y;}
void chmin(ll &x,ll y) {if(x>y) x=y;}
ll mysqr(ll x) {return x*x;}
//*******************全局常量*******************
const int MAXN=510000;
//*******************全局定义*******************
struct Lct
{
int son[2],f;
int d,c;//值、xor和
bool fz;
}p[MAXN];
//*******************实现*******************
void pushup(int x)
{
int lc=p[x].son[0],rc=p[x].son[1];
p[x].c=p[x].d;
if(lc>0) p[x].c^=p[lc].c;
if(rc>0) p[x].c^=p[rc].c;
}
void pushdown(int x)
{
if(!p[x].fz) return;
p[x].fz=0;//debug
swap(p[x].son[0],p[x].son[1]);
int lc=p[x].son[0],rc=p[x].son[1];
p[lc].fz^=1;p[rc].fz^=1;
}
void rotate(int x,int w)
{
int f=p[x].f,ff=p[f].f;
if(ff>0)
{
if(p[ff].son[0]==f) p[ff].son[0]=x;
else if(p[ff].son[1]==f) p[ff].son[1]=x;
}
p[x].f=ff;
int xson=p[x].son[w];
p[f].son[1-w]=xson;
if(xson>0) p[xson].f=f;
p[x].son[w]=f;
p[f].f=x;
pushup(f);
pushup(x);
}
bool isrt(int x,int rt)
{
return (p[x].f==rt)or(p[p[x].f].son[0]!=x and p[p[x].f].son[1]!=x);
}
int lst[MAXN];
void splay(int x,int rt)
{
int t=x,s=0;
while(!isrt(t,rt)) lst[++s]=t,t=p[t].f;
lst[++s]=t;while(s>0) pushdown(lst[s--]);
while(!isrt(x,rt))
{
int f=p[x].f,ff=p[f].f;
if(isrt(f,rt))
{
if(p[f].son[0]==x) rotate(x,1);
else if(p[f].son[1]==x) rotate(x,0);
return;
}
if(p[ff].son[0]==f and p[f].son[0]==x) rotate(f,1),rotate(x,1);
else if(p[ff].son[0]==f and p[f].son[1]==x) rotate(x,0),rotate(x,1);
else if(p[ff].son[1]==f and p[f].son[0]==x) rotate(x,1),rotate(x,0);
else if(p[ff].son[1]==f and p[f].son[1]==x) rotate(f,0),rotate(x,0);
}
}
void access(int x)
{
int y=0;
while(x>0)
{
splay(x,0);
p[x].son[1]=y;
pushup(x);
y=x;x=p[x].f;
}
}
void makeroot(int x)
{
access(x);
splay(x,0);
p[x].fz^=1;
}
void splity(int x,int y)
{
makeroot(x);
access(y);
splay(y,0);
}
int findrt(int x)
{
access(x);
splay(x,0);
while(1)
{
pushdown(x);//debug
if(!p[x].son[0]) break;
x=p[x].son[0];
}
splay(x,0);//速度
return x;
}
void link(int x,int y)
{
makeroot(y);
p[y].f=x;
}
void cut(int x,int y)
{
splity(x,y);
if(p[y].son[0]!=x or (p[y].son[0]==x and p[x].son[1]>0)) return;
p[p[y].son[0]].f=0;//debug
p[y].son[0]=0;
pushup(y);//debug
}
//*******************主函数*******************
int d[MAXN];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i].d);
p[i].c=p[i].d;
p[i].son[0]=p[i].son[1]=p[i].f=0;
p[i].fz=0;
}
while(m--)
{
int op,x,y;scanf("%d%d%d",&op,&x,&y);
if(op==0)
{
splity(x,y);
printf("%d\n",p[y].c);
}
if(op==1)
{
if(findrt(x)!=findrt(y)) link(x,y);
}
if(op==2)
{
if(findrt(x)==findrt(y)) cut(x,y);
}
if(op==3)
{
splay(x,0);
p[x].d=y;
pushup(x);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/动态树.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%