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

[HONI 2025/2026 #4] Magija

Magija

题目描述

魔术师 Ivor 请来了 nn 名志愿者,将他们从左到右排成一列。初始时,编号为 xx 的人站在位置 xx。

Ivor 可以学习一种用三个整数 l,r,lenl,r,\mathrm{len} 表示的技巧:将两个不相交、长度相同的位置区间 [l,l+len−1][l,l+\mathrm{len}-1] 和 [r,r+len−1][r,r+\mathrm{len}-1] 按对应位置交换。也就是说,对每个 0≤i<len0\le i<\mathrm{len},同时交换位置 l+il+i 与 r+ir+i 上的人。交换不会颠倒任一区间内部的顺序。

按时间顺序给出 qq 个事件,分为两种:

  • 1 x:考虑目前已经学会的所有技巧,求编号为 xx 的人能够到达的最小位置和最大位置。技巧可以使用任意多次,顺序任意,也可以不使用某些技巧。
  • 2 l r len:Ivor 学会一种新的交换技巧。

每次询问都从初始排列出发,只考虑此前已经学会的技巧。询问本身不改变排列,也不会取消已经学会的技巧。

输入格式

第一行包含两个整数 n,qn,q。

接下来 qq 行,每行描述一个事件,格式为 1 x 或 2 l r len。

输出格式

对于每个类型为 1 的事件,输出一行两个整数,依次表示该志愿者能够到达的最小位置和最大位置。

数据范围

  • 1≤n,q≤2×1051\le n,q\le2\times10^5。
  • 对于询问,1≤x≤n1\le x\le n。
  • 对于交换技巧,1≤l<r≤n1\le l<r\le n、1≤len≤n1\le\mathrm{len}\le n、l+len−1<rl+\mathrm{len}-1<r 且 r+len−1≤nr+\mathrm{len}-1\le n。
子任务 分值 附加限制
1 9 n,q≤5n,q\le5
2 14 n,q≤15n,q\le15
3 22 n,q≤1000n,q\le1000
4 11 n≤4000n\le4000
5 17 n≤10000n\le10000
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 说明

技巧可以交换区间 [1,2][1,2] 和 [7,8][7,8]。编号为 22 的人可以停留在位置 22,也可以经过一次交换到达位置 88,因此答案为 2 8。