A16604 | Gellyfish and Lycoris Radiata (Easy Version)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
这是该问题的简单版本。不同版本之间的区别在于本版本中 $n$ 和 $q$ 的时间限制及约束更低。
Gellyfish 有一个包含 $n$ 个集合的数组。最初，所有集合都是空的。
现在，Gellyfish 将进行 $q$ 次操作。每次操作包含一次修改操作和一次查询操作，对于第 $i$ 次（$1 \leq i \leq q$）操作：
首先，会有一次修改操作，可能是以下三种之一：
1. 插入操作：给定一个整数 $r$。将元素 $i$ 插入到第 $1$ 到第 $r$ 个集合中。注意，这里插入的元素是 $i$，即操作的编号，而不是集合的编号。
2. 反转操作：给定一个整数 $r$。将第 $1$ 到第 $r$ 个集合的顺序反转。
3. 删除操作：给定一个整数 $x$。从所有包含 $x$ 的集合中删除元素 $x$。
然后进行一次查询操作：
- 查询操作：给定一个整数 $p$。输出第 $p$ 个集合中的最小元素（如果该集合为空，则答案为 $0$）。
现在，Flower 需要为每次查询操作提供答案。请你帮助她！
本题有一个额外的约束：Gellyfish 只有在 Flower 回答了上一次查询操作后，才会给出下一次操作。也就是说，你需要在线处理本题。具体请参考输入格式。
Gellyfish 有一个包含 $n$ 个集合的数组。最初，所有集合都是空的。
现在，Gellyfish 将进行 $q$ 次操作。每次操作包含一次修改操作和一次查询操作，对于第 $i$ 次（$1 \leq i \leq q$）操作：
首先，会有一次修改操作，可能是以下三种之一：
1. 插入操作：给定一个整数 $r$。将元素 $i$ 插入到第 $1$ 到第 $r$ 个集合中。注意，这里插入的元素是 $i$，即操作的编号，而不是集合的编号。
2. 反转操作：给定一个整数 $r$。将第 $1$ 到第 $r$ 个集合的顺序反转。
3. 删除操作：给定一个整数 $x$。从所有包含 $x$ 的集合中删除元素 $x$。
然后进行一次查询操作：
- 查询操作：给定一个整数 $p$。输出第 $p$ 个集合中的最小元素（如果该集合为空，则答案为 $0$）。
现在，Flower 需要为每次查询操作提供答案。请你帮助她！
本题有一个额外的约束：Gellyfish 只有在 Flower 回答了上一次查询操作后，才会给出下一次操作。也就是说，你需要在线处理本题。具体请参考输入格式。
输入格式
第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$），分别表示集合的数量和操作次数。
由于你需要在线响应操作，操作将以编码形式给出。
接下来的 $q$ 行中，第 $i$ 行包含三个整数 $a$、$b$ 和 $c$（$1 \leq a \leq 3$，$1 \leq c \leq n$），描述第 $i$ 次操作的编码形式。
其中，$a$ 表示修改操作的类型。$a=1$ 表示插入操作，$a=2$ 表示反转操作，$a=3$ 表示删除操作。
- 如果 $a=1$，则修改操作为插入操作。保证 $1 \leq b \leq n$。$r$ 的计算方式为 $r=(b+\text{ans}_{i-1}-1) \bmod n + 1$。
- 如果 $a=2$，则修改操作为反转操作。保证 $1 \leq b \leq n$。$r$ 的计算方式为 $r=(b+\text{ans}_{i-1}-1) \bmod n + 1$。
- 如果 $a=3$，则修改操作为删除操作。保证 $1 \leq b \leq q$。$x$ 的计算方式为 $x=(b+\text{ans}_{i-1}-1) \bmod q + 1$。
对于查询操作，$p$ 的计算方式为 $p = (c+\text{ans}_{i-1}-1) \bmod n + 1$。
其中 $\text{ans}_i (1 \leq i \leq q)$ 表示第 $i$ 次操作查询的答案。并且定义 $\text{ans}_0 = 0$。
由于你需要在线响应操作，操作将以编码形式给出。
接下来的 $q$ 行中，第 $i$ 行包含三个整数 $a$、$b$ 和 $c$（$1 \leq a \leq 3$，$1 \leq c \leq n$），描述第 $i$ 次操作的编码形式。
其中，$a$ 表示修改操作的类型。$a=1$ 表示插入操作，$a=2$ 表示反转操作，$a=3$ 表示删除操作。
- 如果 $a=1$，则修改操作为插入操作。保证 $1 \leq b \leq n$。$r$ 的计算方式为 $r=(b+\text{ans}_{i-1}-1) \bmod n + 1$。
- 如果 $a=2$，则修改操作为反转操作。保证 $1 \leq b \leq n$。$r$ 的计算方式为 $r=(b+\text{ans}_{i-1}-1) \bmod n + 1$。
- 如果 $a=3$，则修改操作为删除操作。保证 $1 \leq b \leq q$。$x$ 的计算方式为 $x=(b+\text{ans}_{i-1}-1) \bmod q + 1$。
对于查询操作，$p$ 的计算方式为 $p = (c+\text{ans}_{i-1}-1) \bmod n + 1$。
其中 $\text{ans}_i (1 \leq i \leq q)$ 表示第 $i$ 次操作查询的答案。并且定义 $\text{ans}_0 = 0$。
输出格式
对于每次查询操作，输出查询的答案。
输入输出样例
输入 #1
5 10 1 2 2 2 3 1 1 5 3 2 2 5 1 5 2 2 4 4 3 2 2 3 1 2 3 10 5 3 2 4
输出 #1
1 0 1 1 3 1 0 5 0 0
所有集合一开始都是空的，因此数组为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$。
根据前述的解码方法，我们可以看到每次操作的变化：
1. 第一次操作：$a=1, r=2, p=2$。修改操作为插入操作，将元素 $1$ 插入到前两个集合中，数组变为 $[\{1\}, \{1\}, \{\}, \{\}, \{\}]$，第二个集合的最小元素为 $1$。
2. 第二次操作：$a=2, r=4, p=2$。修改操作为反转操作，将前四个集合反转，数组变为 $[\{\}, \{\}, \{1\}, \{1\}, \{\}]$，第二个集合为空，答案为 $0$。
3. 第三次操作：$a=1, r=5, p=3$。修改操作为插入操作，将元素 $3$ 插入到所有集合中，数组变为 $[\{3\}, \{3\}, \{1, 3\}, \{1, 3\}, \{3\}]$，第三个集合的最小元素为 $1$。
4. 第四次操作：$a=2, r=3, p=1$。修改操作为反转操作，将前三个集合反转，数组变为 $[\{1, 3\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$，第一个集合的最小元素为 $1$。
5. 第五次操作：$a=1, r=1, p=3$。修改操作为插入操作，将元素 $5$ 插入到第一个集合，数组变为 $[\{1, 3, 5\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$，第三个集合的最小元素为 $3$。
6. 第六次操作：$a=2, r=2, p=2$。修改操作为反转操作，将前两个集合反转，数组变为 $[\{3\}, \{1, 3, 5\}, \{3\}, \{1, 3\}, \{3\}]$，第二个集合的最小元素为 $1$。
7. 第七次操作：$a=3, x=3, p=3$。修改操作为删除操作，从所有集合中删除元素 $3$，数组变为 $[\{\}, \{1, 5\}, \{\}, \{1\}, \{\}]$，第三个集合为空，答案为 $0$。
8. 第八次操作：$a=3, x=1, p=2$。修改操作为删除操作，从所有集合中删除元素 $1$，数组变为 $[\{\}, \{5\}, \{\}, \{\}, \{\}]$，第二个集合的最小元素为 $5$。
9. 第九次操作：$a=3, x=5, p=5$。修改操作为删除操作，从所有集合中删除元素 $5$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$，第五个集合为空，答案为 $0$。
10. 第十次操作：$a=3, x=2, p=4$。修改操作为删除操作，从所有集合中删除元素 $2$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$，第四个集合为空，答案为 $0$。
请注意，虽然我们没有将元素 $2$ 插入到集合中，但在第十次操作中依然从所有集合中删除了元素 $2$，这说明删除操作不要求被删除的元素一定存在于集合中。同时也说明可能会有两次删除操作删除同一个元素。
根据前述的解码方法，我们可以看到每次操作的变化：
1. 第一次操作：$a=1, r=2, p=2$。修改操作为插入操作，将元素 $1$ 插入到前两个集合中，数组变为 $[\{1\}, \{1\}, \{\}, \{\}, \{\}]$，第二个集合的最小元素为 $1$。
2. 第二次操作：$a=2, r=4, p=2$。修改操作为反转操作，将前四个集合反转，数组变为 $[\{\}, \{\}, \{1\}, \{1\}, \{\}]$，第二个集合为空，答案为 $0$。
3. 第三次操作：$a=1, r=5, p=3$。修改操作为插入操作，将元素 $3$ 插入到所有集合中，数组变为 $[\{3\}, \{3\}, \{1, 3\}, \{1, 3\}, \{3\}]$，第三个集合的最小元素为 $1$。
4. 第四次操作：$a=2, r=3, p=1$。修改操作为反转操作，将前三个集合反转，数组变为 $[\{1, 3\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$，第一个集合的最小元素为 $1$。
5. 第五次操作：$a=1, r=1, p=3$。修改操作为插入操作，将元素 $5$ 插入到第一个集合，数组变为 $[\{1, 3, 5\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$，第三个集合的最小元素为 $3$。
6. 第六次操作：$a=2, r=2, p=2$。修改操作为反转操作，将前两个集合反转，数组变为 $[\{3\}, \{1, 3, 5\}, \{3\}, \{1, 3\}, \{3\}]$，第二个集合的最小元素为 $1$。
7. 第七次操作：$a=3, x=3, p=3$。修改操作为删除操作，从所有集合中删除元素 $3$，数组变为 $[\{\}, \{1, 5\}, \{\}, \{1\}, \{\}]$，第三个集合为空，答案为 $0$。
8. 第八次操作：$a=3, x=1, p=2$。修改操作为删除操作，从所有集合中删除元素 $1$，数组变为 $[\{\}, \{5\}, \{\}, \{\}, \{\}]$，第二个集合的最小元素为 $5$。
9. 第九次操作：$a=3, x=5, p=5$。修改操作为删除操作，从所有集合中删除元素 $5$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$，第五个集合为空，答案为 $0$。
10. 第十次操作：$a=3, x=2, p=4$。修改操作为删除操作，从所有集合中删除元素 $2$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$，第四个集合为空，答案为 $0$。
请注意，虽然我们没有将元素 $2$ 插入到集合中，但在第十次操作中依然从所有集合中删除了元素 $2$，这说明删除操作不要求被删除的元素一定存在于集合中。同时也说明可能会有两次删除操作删除同一个元素。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？