CF896C Willem, Chtholly and Seniorious
题目描述
——威廉……
——怎么了?
——好像瑟尼欧里斯出问题了……
——我去看看……

瑟尼欧里斯是通过特定顺序连接特殊护符制成的。
经过了 500 多年,这把圣剑现在状况不太好,所以威廉决定彻底检查它。
瑟尼欧里斯有 n 片护符。威廉将它们排成一行,第 i 片护符上写着一个整数 ai。
为了维护它,威廉需要执行 m 次操作。每次操作是以下四种类型之一:
∙类型 1:给定 l,r,x,对于所有 l≦i≦r,将 ai 增加 x;
∙类型 2:给定 l,r,x,对于所有 l≦i≦r,将 ai 赋值为 x;
∙类型 3:给定 l,r,x,将 al,al+1,…,ar 从小到大排序后,输出第 x 个数。保证 1≦x≦r−l+1;
∙类型 4:给定 l,r,x,y,输出 (i=l∑raix)mody。
输入格式
输入只有一行,包含四个整数 $n,m,\mathrm{seed},\mathrm{vmax}\left(1 \leqq n,m \leqq 10^5;\ 0 \leqq \mathrm{seed} \lt 10^9+7;\ 1 \leqq \mathrm{vmax} \leqq 10^9\right)$,分别代表护符数量、操作次数、随机种子和数值上限。
初始数组与全部操作都由下面的伪代码生成:
def rnd():
ret = seed
seed = (seed * 7 + 13) mod 1000000007
return ret
for i = 1 to n:
a[i] = (rnd() mod vmax) + 1
for i = 1 to m:
op = (rnd() mod 4) + 1
l = (rnd() mod n) + 1
r = (rnd() mod n) + 1
if (l > r):
swap(l, r)
if (op == 3):
x = (rnd() mod (r - l + 1)) + 1
else:
x = (rnd() mod vmax) + 1
if (op == 4):
y = (rnd() mod vmax) + 1
伪代码中各个变量的含义与范围如下:
∙n:护符数量,1≦n≦105;
∙m:操作次数,1≦m≦105;
∙seed:随机种子,0≦seed<109+7。每次调用 rnd() 都会先返回当前的 seed,再将 seed 更新为 $(\mathrm{seed} \times 7+13) \bmod \left(10^9+7\right)$;
∙vmax:数值上限,1≦vmax≦109。初始值 ai、类型 1 和类型 2 的 x、类型 4 的 y 都在 [1,vmax] 内。
伪代码依次生成 a1,a2,…,an,随后依次生成 m 次操作的 op,l,r,x;当 op=4 时还会额外生成 y。生成的 l,r 满足 1≦l≦r≦n。
输出格式
对于每一次类型为 3 或 4 的操作,新起一行输出一个整数,代表该次操作的答案。类型为 1 或 2 的操作不会产生输出。
测试样例
10 10 7 9
2
1
0
3
样例 1 解释
按照伪代码生成,初始数组为 {8,9,7,2,3,1,5,6,4,8},10 次操作依次为:
∙类型 2:l=6,r=7,x=9;
∙类型 1:l=3,r=10,x=8;
∙类型 4:l=4,r=6,x=2,y=4;
∙类型 1:l=4,r=5,x=8;
∙类型 2:l=1,r=7,x=1;
∙类型 4:l=7,r=9,x=4,y=4;
∙类型 1:l=2,r=7,x=9;
∙类型 4:l=5,r=8,x=1,y=1;
∙类型 2:l=5,r=7,x=5;
∙类型 4:l=3,r=10,x=8,y=5。
其中第 3,6,8,10 次操作都是类型 4,输出的答案依次为 2,1,0,3。
10 10 9 9
1
1
3
3