ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 I: 学排列导致的x

内存限制：1024 MB 时间限制：4 S
题面：传统 评测方式：Special Judge 上传者：
提交：3 通过：2
返回比赛提交提交记录

题目描述

一个 1 ~ k 的排列 p 是一个 k 元组 (p1, p2, …, pk)，其中整数 1 ~ k 在 p 中各出现一次。
对于任意两个 1 ~ k 的排列 u, v，我们定义一个运算 u ⊕ v，其结果为一个 1 ~ k 的排列 w，满足 wi = uv [i] 。例如，(1, 3, 2) ⊕ (2, 3, 1) = (3, 2, 1)。
yummy 有 n 个 1 ~ k 的排列 p1, p2, …, pn ，你需要依次实现 m 个操作，分为两种：

  • 2 l x r ，对于每个 l ≤ i ≤ r ，把 pi 的一个后缀平移到最前面，使得 pi 的第一项是 x 。
  • 1 i x z ，询问 pi ⊕ pz 的第 x 项。

输入格式

为了减少读入量，排列将随机生成。正解和排列生成方式无关。
输入的第一行有四个正整数 n, m, k, Seed（1 ≤ n, m ≤ 2 × 10⁵, 1 ≤ k ≤ 30, 0 ≤ Seed < 2⁶⁴），表示排列个数、询问个数、排列元素个数和随机数种子。
生成初始 p 的 C++ 代码如下，其中 Seed 即为第一行读入的数字：




unsigned long long Seed
; unsigned myrand(){Seed^=Seed<<5;Seed^=Seed>>13;Seed^=Seed<<3;return Seed;} 
//template< typename T > void swap(T &u,T &v){T t=u;u=v;v=t;} //如选手未手动调用 algorithm 库, 请取消注释本行
 template< typename T > void generate(int k,T p[]){//k 为题目中的 k, p[] 为产生的排列储位, 下标从 1 开始 
                auto q=p+1; 
                 for(int i=1;i<=k;++i)q[i]=i; 
                 for(int i=1;i<=k;++i)swap(q[i],q[myrand()%k+1]);
 }


具体地，选手将这段代码复制到程序的开头，读入 Seed 后连续调用 n 次 generate (k, p) 得到 n 个排列，其中第 i 次调用函数得到的排列即为 pi 。
接下来会有 m 行，每行有四个正整数 op, l, r, x（op ∈ {1, 2}，1 ≤ l ≤ r ≤ n，1 ≤ x ≤ k ）表示一次操作，含义同题目描述。

输出格式

对于每个 op = 1 的操作，输出一行一个正整数表示答案。

输入样例 复制 

3 5 4 998244353
1 1 3 1
2 3 3 2
1 3 3 3
2 1 3 3
1 2 3 1

输出样例 复制 

2
4
4

数据范围与提示

【样例解释】
生成的 3 个排列依次为 p1 = (3, 4, 2, 1), p2 = (2, 4, 1, 3), p3 = (4, 1, 2, 3)。

  • 第一个操作中，p1 ⊕ p3 等于 (2, 4, 1, 3)，第 1 项是 2，因此回答 2。
  • 第二个操作中，把 p3 的第一项变成 2，因此 p3 变成了 (2, 3, 4, 1)。
  • 第三个操作中，p3 = (2, 3, 4, 1)，第 3 项是 4。
  • 第四个操作中，把 p1, p2, p3 的第一项都变成 3，三个排列分别变成 (3, 4, 2, 1), (3, 2, 4, 1), (3, 4, 1, 2)。
  • 最后一个中，p2 ⊕ p3 等于 (4, 1, 3, 2)，因此回答 4。