HONI2526R4#magija. [HONI 2025/2026 #4] Magija
[HONI 2025/2026 #4] Magija
Magija

题目描述
魔术师 Ivor 请来了 名志愿者,将他们从左到右排成一列。初始时,编号为 的人站在位置 。
Ivor 可以学习一种用三个整数 表示的技巧:将两个不相交、长度相同的位置区间 和 按对应位置交换。也就是说,对每个 ,同时交换位置 与 上的人。交换不会颠倒任一区间内部的顺序。
按时间顺序给出 个事件,分为两种:
1 x:考虑目前已经学会的所有技巧,求编号为 的人能够到达的最小位置和最大位置。技巧可以使用任意多次,顺序任意,也可以不使用某些技巧。2 l r len:Ivor 学会一种新的交换技巧。
每次询问都从初始排列出发,只考虑此前已经学会的技巧。询问本身不改变排列,也不会取消已经学会的技巧。
输入格式
第一行包含两个整数 。
接下来 行,每行描述一个事件,格式为 1 x 或 2 l r len。
输出格式
对于每个类型为 1 的事件,输出一行两个整数,依次表示该志愿者能够到达的最小位置和最大位置。
数据范围
- 。
- 对于询问,。
- 对于交换技巧,、、 且 。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 9 | |
| 2 | 14 | |
| 3 | 22 | |
| 4 | 11 | |
| 5 | 17 | |
| 6 | 37 | 无附加限制 |
样例
5 3
2 3 4 1
1 5
1 3
5 5
3 4
9 2
2 1 7 2
1 2
2 8
样例 2 说明
技巧可以交换区间 和 。编号为 的人可以停留在位置 ,也可以经过一次交换到达位置 ,因此答案为 2 8。