#Algo2012. 【模板】动态树(LCT)

    ID: 299 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构动态树图论树链剖分luogu模板

【模板】动态树(LCT)

题目描述

给定 nn 个点以及每个点的权值,要你处理接下来的 mm 个操作。
操作有四种,操作从 0033 编号。点从 11nn 编号。

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

输入格式

第一行两个整数,分别为 nnmm,代表点数和操作数。

接下来 nn 行,每行一个整数,第 (i+1)(i + 1) 行的整数 aia_i 表示节点 ii 的权值。

接下来 mm 行,每行三个整数,分别代表操作类型和操作所需的量。

输出格式

对于每一个 00 号操作,你须输出一行一个整数,表示 xxyy 的路径上点权的 xor\text{xor} 和。

3 3 
1
2
3
1 1 2
0 1 2 
0 1 1
3
1
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
624
315
296
232709
232823

提示

数据规模与约定

对于全部的测试点,保证:

  • 1n1051 \leq n \leq 10^51m3×1051 \leq m \leq 3 \times 10^51ai1091 \leq a_i \leq 10^9
  • 对于操作 0,1,20, 1, 2,保证 1x,yn1 \leq x, y \leq n
  • 对于操作 33,保证 1xn1 \leq x \leq n1y1091 \leq y \leq 10^9