QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 512 MB Total points: 100
[-3]

# 5410. 树特卡克林

Statistics

给定一棵包含 n 个点的由有根树构成的森林(初始没有边,每个顶点是一棵有根树的根),顶点由 1n 的整数编号表示。你需要维护森林的轻重链剖分结构,具体如下:

对每个顶点 ω1ωn),记其孩子构成的集合为 children(ω)。对于每个 ω,若 ω 不是根,则记其父亲为 father(ω)

一个顶点 ω 的子树规模 size(ω) 定义为 1+uchildren(ω)size(u)

一个顶点 ω 如果不是叶子(即 children(ω)),则它的重孩子 he(ω) 被定义为 argmaxuchildren(ω)size(u)n+max(u,he(u),he(he(u)),),即子树规模最大的孩子(若有多个孩子 u 的子树规模相同,则取以 u 为根的子树中,u 所在的重链中最大的编号最大);

重链是一个由顶点构成的序列 \omega_1, \omega_2, \cdots, \omega_k(k > 0),满足条件:

  • \omega_1 是根或 \omega_1 \ne \mathrm{he}(\mathrm{father}(\omega_1))
  • \omega_i = \mathrm{he}(\omega_{i-1}) (2 \leq i \leq k)

对一棵树,每个顶点恰好属于一条重链。重链的权值为 \omega_1 \oplus \omega_2 \oplus \cdots \oplus \omega_k,即序列中顶点编号的按位异或和。

需要依次进行 2m 次操作,操作类型如下:

  • 加边:给出两个顶点 a, b,令 b 成为 b 所在有根树的根(设定点构成的序列 t_1, t_2, \cdots, t_l 满足 t_l = bt_1 为根,(t_i, t_{i+1}), 1 \leq i < lb 所在有根树上的有向边,将这些边反转为 (t_{i+1}, t_i) 即可令 b 成为根),然后加入 ab 的有向边 (a, b),保证操作前 a,b 在不同的有根树上。
  • 删边:给出两个顶点 a, b,删除 a, b 间的有向边(可能为 (a, b)(b, a)),保证这条边之前存在。
  • 查询:给出一个整数 k,设当前共有 N 条重链,询问当前存在的所有重链按权值从小到大排序后,第 ((k-1) \bmod N)+1 小的权值。

输入格式

第一行有两个整数 n, m

接下来 m 行,每行四个整数 o\;a\;b\;k,若 o=1 则表示先加边 a, b 然后查询 k,若 o=0 则表示先删边 a,b 然后查询 k

输出格式

m 行,每行一个整数,依次为每次查询操作的结果。

样例数据

样例输入

5 10
1 1 2 3
1 2 3 3
1 2 4 3
1 3 5 3
0 2 3 3
1 1 3 3
0 1 2 3
1 2 3 3
0 3 5 3
1 1 5 3

样例输出

4
5
7
4
6
6
6
4
5
4

子任务

31 个测试点,所有测试点满足 1 \leq n \leq 10^51 \leq m \leq 5 \times 10^50 \leq o \leq 11 \leq a,b,k \leq nn,m,o,a,b,k 均为整数。

测试点可能具有以下性质:

  • 性质 1:操作使用以下策略随机生成,重复直到生成了 m 行的操作序列。
    • [1,n] 中等概率随机选取三个整数 x,y,k,若 x,y 在不同的有根树上,则生成一行 1 x y k,否则若 x 不是根,等概率地生成一行 0 x father(x) k0 father(x) x k 之一,否则不进行操作。
  • 性质 2:m=n-1,且对 2 \leq i \leq n,数据的第 i 行为 1 a i k,其中 a[1,i-1] 中的整数等概率选取。
  • 性质 3:m=n-1,且对 2 \leq i \leq n,数据的第 i 行为 1 i b k,其中 b[1,i-1] 中的整数等概率选取。

每个测试点的性质如下。

  • 子任务 1(5 分):测试点 1,n=10, m=50,满足性质 1。
  • 子任务 2(5 分):测试点 2,n=100, m=500,满足性质 1。
  • 子任务 3(10 分):测试点 3,n=1\,000, m=5\,000,满足性质 1。
  • 子任务 4(10 分):测试点 4,满足性质 2。
  • 子任务 5(10 分):测试点 5,满足性质 3。
  • 子任务 6(20 分):测试点 6-10,满足性质 1。
  • 子任务 7(40 分):测试点 11-31,没有特殊限制。