A5959. 「RCOI2019」维护
编程题
省选/NOI-
知识点
题目描述
**题目来源：[「RCOI2019」Rochine Round 1](https://www.luogu.com.cn/contest/20511)**
维护一颗以 $1$ 为根的树的形态，要求支持插入叶子节点、删除任意结点以及查询 $k$ 代祖先。为了尽量简单，删除时，直接让这个点的儿子替代它就好（即，全部接到父节点上）。初始时，树仅有根节点 $1$。
维护一颗以 $1$ 为根的树的形态，要求支持插入叶子节点、删除任意结点以及查询 $k$ 代祖先。为了尽量简单，删除时，直接让这个点的儿子替代它就好（即，全部接到父节点上）。初始时，树仅有根节点 $1$。
输入格式
第一行两个整数 $q$ 和 $\text{online}$。$q$ 表示操作数，$\text{online}=1$ 说明本测试点强制在线。
**请认真阅读下面的输入格式，稍有不慎即会 WA**。
**对于三种操作， 若询问的 $x$ 已经被删除或 $x$ 大于节点总数或 $x=0$，则 $\text{lastans}$ 也不要更新。**
接下来 $q$ 行，分为三种情况（$\text{lastans}$ 初值为 $0$）：
- 插入操作，格式为
- 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$；
- 然后，增加一个编号为已经加入过的结点总数 $+1$ 的节点作为 $x$ 的儿子。
- 若 $\text{online}=1$，则 $\text{lastans}$ 更新为 $x$，若 $x$ 已经被删除则不应新增任何节点。
- 删除操作，格式为
- 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$；
- 然后删除 $x$，若不存在请忽略。
- 若 $\text{online}=1$，则 $\text{lastans}$ 更新为 $x$ 的父亲，保证 $x\ne 1$。
- 查询操作，格式为
- 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$，$y\leftarrow y\ \mathrm{xor}\ \text{lastans}$；
- 然后输出 $x$ 的 $y$ 代祖先。
- 若 $\text{online}=1$，则 $\text{lastans}$ 更新为答案，若 $x$ 被删除了则什么都不要输出，若不存在则答案为 $0$。
**请认真阅读下面的输入格式，稍有不慎即会 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
输出 #1
2 1 0
输入 #2
4 0 1 1 2 2 3 2 0 3 1 0
输出 #2
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
输出 #3
2 1 2 0 3 7 11 7 8
说明/提示
对于所有数据，$1\le q\le 2\times 10^5,\text{online}\in\{0,1\}$。详细数据范围如下。
| 测试点编号 | $q$ | $\text{online}$ | 特殊性质 | 每测试点分数 |
| :---------: | :------------: | :-------------: | :----------: | :----------: |
| $1\sim 3$ | $20$ | $1$ | 数据随机生成 | $3$ |
| $4,5$ | $20$ | $0$ | 数据随机生成 | $3$ |
| $6\sim 8$ | $200$ | $1$ | 数据随机生成 | $3$ |
| $9,10$ | $200$ | $0$ | 数据随机生成 | $3$ |
| $11,12$ | $2\times 10^4$ | $1$ | 数据随机生成 | $3$ |
| $13\sim 15$ | $2\times 10^4$ | $0$ | 数据随机生成 | $3$ |
| $16\sim 19$ | $2\times 10^5$ | $0$ | 无 | $4$ |
| $20$ | $2\times 10^5$ | $1$ | 无删除操作 | $9$ |
| $21\sim 25$ | $2\times 10^5$ | $1$ | 无 | $6$ |
对于 $q\le 2\times 10^4$ 的测试点，按点计分；其他测试点，按特殊性质对应 Subtask **捆绑计分**。
| 测试点编号 | $q$ | $\text{online}$ | 特殊性质 | 每测试点分数 |
| :---------: | :------------: | :-------------: | :----------: | :----------: |
| $1\sim 3$ | $20$ | $1$ | 数据随机生成 | $3$ |
| $4,5$ | $20$ | $0$ | 数据随机生成 | $3$ |
| $6\sim 8$ | $200$ | $1$ | 数据随机生成 | $3$ |
| $9,10$ | $200$ | $0$ | 数据随机生成 | $3$ |
| $11,12$ | $2\times 10^4$ | $1$ | 数据随机生成 | $3$ |
| $13\sim 15$ | $2\times 10^4$ | $0$ | 数据随机生成 | $3$ |
| $16\sim 19$ | $2\times 10^5$ | $0$ | 无 | $4$ |
| $20$ | $2\times 10^5$ | $1$ | 无删除操作 | $9$ |
| $21\sim 25$ | $2\times 10^5$ | $1$ | 无 | $6$ |
对于 $q\le 2\times 10^4$ 的测试点，按点计分；其他测试点，按特殊性质对应 Subtask **捆绑计分**。