QOJ.ac

QOJ

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

# 5410. 树特卡克林

统计

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

对每个顶点 $\omega$($1 \leq \omega \leq n$),记其孩子构成的集合为 $\mathrm{children}(\omega)$。对于每个 $\omega$,若 $\omega$ 不是根,则记其父亲为 $\mathrm{father}(\omega)$。

一个顶点 $\omega$ 的子树规模 $\mathrm{size}(\omega)$ 定义为 $1 + \displaystyle\sum_{u \in \mathrm{children}(\omega)} \mathrm{size}(u)$

一个顶点 $\omega$ 如果不是叶子(即 $\mathrm{children}(\omega) \ne \varnothing$),则它的重孩子 $\mathrm{he}(\omega)$ 被定义为 $\displaystyle \arg \max_{u \in \mathrm{children}(\omega)} \mathrm{size}(u) \cdot n + \max(u, \mathrm{he}(u), \mathrm{he}(\mathrm{he}(u)), \cdots)$,即子树规模最大的孩子(若有多个孩子 $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 = b$ 且 $t_1$ 为根,$(t_i, t_{i+1}), 1 \leq i < l$ 是 $b$ 所在有根树上的有向边,将这些边反转为 $(t_{i+1}, t_i)$ 即可令 $b$ 成为根),然后加入 $a$ 到 $b$ 的有向边 $(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^5$,$1 \leq m \leq 5 \times 10^5$,$0 \leq o \leq 1$,$1 \leq a,b,k \leq n$,$n,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,没有特殊限制。