QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21529. 动态树(简单版)

统计

题目描述

给定 $n$ 个点以及每个点的权值,要你处理接下来的 $m$ 个操作。

操作有四种,操作从 $0$ 到 $3$ 编号。点从 $1$ 到 $n$ 编号。

  • 0 x y 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\text{xor}$ 和。若路径不存在输出 $-1$。
  • 1 x y 代表连接 $x$ 到 $y$,若 $x$ 到 $y$ 已经联通则无需连接。
  • 2 x y 代表删除边 $(x,y)$,不保证边 $(x,y)$ 存在。
  • 3 x y 代表将点 $x$ 上的权值变成 $y$。

输入格式

第一行两个整数,分别为 $n$ $(1 \leq n \leq 150,000)$ 和 $m$ $(1 \leq m \leq 300,000)$,代表点数和操作数。

接下来 $n$ 行,每行一个整数,整数在 $[1,10^9]$ 内,代表每个点的权值。

然后有 $m$ 行,每行三个整数,分别代表操作类型和操作所需的量。

输出格式

对于每一个 $0$ 号操作,你须输出一行一个整数,表示 $x$ 到 $y$ 的路径上点权的 $\text{xor}$ 和。若不存在输出 $-1$。

样例数据

样例 1 输入

3 3 
1
2
3
1 1 2
0 1 2 
0 1 1

样例 1 输出

3
1

样例 2 输入

5 14
114 514 19 19 810
1 1 2
0 1 2
2 1 2
1 1 2
1 2 3
2 1 3
1 1 3
1 4 5
1 2 5
0 3 5
0 3 4
3 5 233333
0 1 5
0 2 5

样例 2 输出

624
315
296
232709
232823

样例 3 输入

10 50
44 61 37 67 60 1 68 68 70 69 
1 8 2
1 5 3
1 2 1
1 9 8
1 1 1
1 3 2
1 2 1
1 8 2
1 3 1
1 1 1
0 10 6
3 9 98
3 2 35
0 9 7
3 6 36
1 9 1
0 10 6
1 3 1
1 4 1
0 7 6
3 1 39
3 7 38
1 8 3
0 4 1
3 1 51
1 8 1
1 2 1
1 4 1
1 4 2
1 8 1
1 10 8
2 4 1
0 6 5
3 8 57
2 5 1
1 9 2
2 8 6
0 10 1
0 4 1
2 4 1
3 6 96
0 6 2
0 3 1
1 1 1
3 5 50
1 5 1
0 3 1
2 6 1
2 5 1
1 10 9

样例 3 输出

-1
-1
-1
-1
100
-1
108
-1
-1
53
53