[AdditionalFile6710.zip](file://AdditionalFile6710.zip?type=additional_file)

#6710. 「RCOI2019」维护

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目来源：「RCOI2019」Rochine Round 1

维护一颗以 $1$ 为根的树的形态，要求支持插入叶子节点、删除任意结点以及查询 $k$ 代祖先。为了尽量简单，删除时，直接让这个点的儿子替代它就好（即，全部接到父节点上）。初始时，树仅有根节点 $1$。

输入格式

第一行两个整数 $q$ 和 $\text{online}$。$q$ 表示操作数，$\text{online}=1$ 说明本测试点强制在线。

请认真阅读下面的输入格式，稍有不慎即会 WA。

对于三种操作， 若询问的 $x$ 已经被删除或 $x$ 大于节点总数或 $x=0$，则 $\text{lastans}$ 也不要更新。

接下来 $q$ 行，分为三种情况（$\text{lastans}$ 初值为 $0$）：

• 插入操作，格式为 1 x：

  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$；
  • 然后，增加一个编号为已经加入过的结点总数 $+1$ 的节点作为 $x$ 的儿子。
  • 若 $\text{online}=1$，则 $\text{lastans}$ 更新为 $x$，若 $x$ 已经被删除则不应新增任何节点。

• 删除操作，格式为 2 x：

  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$；
  • 然后删除 $x$，若不存在请忽略。
  • 若 $\text{online}=1$，则 $\text{lastans}$ 更新为 $x$ 的父亲，保证 $x\ne 1$。

• 查询操作，格式为 3 x y：

  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$，$y\leftarrow y\ \mathrm{xor}\ \text{lastans}$；
  • 然后输出 $x$ 的 $y$ 代祖先。
  • 若 $\text{online}=1$，则 $\text{lastans}$ 更新为答案，若 $x$ 被删除了则什么都不要输出，若不存在则答案为 $0$。

输出格式

输出一些行，每行一个整数，表示询问的答案。

样例 1

输入

8 0
1 1
1 2
1 3
3 4 2
2 3
3 4 2
2 2
3 4 2

输出

2
1
0

样例 2

输入

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

输出

1

样例 3

输入

20 1
1 1
1 3
1 1
3 7 1
3 6 1
3 5 3
1 6
1 1
1 1
1 3
3 15 1
3 8 3
3 11 2
1 1
1 14
1 0
1 3
3 7 10
3 7 8
3 11 5

输出

2
1
2
0
3
7
11
7
8

数据范围与提示

对于所有数据，$1\le q\le 2\times 10^5,\text{online}\in\{0,1\}$。详细数据范围如下。

对于 $q\le 2\times 10^4$ 的测试点，按点计分；其他测试点，按特殊性质对应 Subtask 捆绑计分。