← 返回题目
题库练习 「RCOI2019」维护
← 上一题 下一题 →

A5959 | 「RCOI2019」维护

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

**题目来源：[「RCOI2019」Rochine Round 1](https://www.luogu.com.cn/contest/20511)**

维护一颗以 $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
输出 #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
C++ 编辑器
输入
输出