#CF896C. 珂朵莉

珂朵莉

CF896C Willem, Chtholly and Seniorious

题目描述

\hspace{15pt}——威廉……

\hspace{15pt}——怎么了?

\hspace{15pt}——好像瑟尼欧里斯出问题了……

\hspace{15pt}——我去看看……

\hspace{15pt}瑟尼欧里斯是通过特定顺序连接特殊护符制成的。

\hspace{15pt}经过了 500500 多年,这把圣剑现在状况不太好,所以威廉决定彻底检查它。

\hspace{15pt}瑟尼欧里斯有 nn 片护符。威廉将它们排成一行,第 ii 片护符上写着一个整数 aia_i。

\hspace{15pt}为了维护它,威廉需要执行 mm 次操作。每次操作是以下四种类型之一:

∙ \hspace{23pt}\bullet\,类型 11:给定 l,r,xl,r,x,对于所有 l≦i≦rl \leqq i \leqq r,将 aia_i 增加 xx;

∙ \hspace{23pt}\bullet\,类型 22:给定 l,r,xl,r,x,对于所有 l≦i≦rl \leqq i \leqq r,将 aia_i 赋值为 xx;

∙ \hspace{23pt}\bullet\,类型 33:给定 l,r,xl,r,x,将 al,al+1,…,ara_l,a_{l+1},\dots,a_r 从小到大排序后,输出第 xx 个数。保证 1≦x≦r−l+11 \leqq x \leqq r-l+1;

∙ \hspace{23pt}\bullet\,类型 44:给定 l,r,x,yl,r,x,y,输出 (∑i=lraix) mod y\left(\sum\limits_{i=l}^{r} a_i^x\right) \bmod y。

输入格式

\hspace{15pt}输入只有一行,包含四个整数 $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)$,分别代表护符数量、操作次数、随机种子和数值上限。

\hspace{15pt}初始数组与全部操作都由下面的伪代码生成:

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

\hspace{15pt}伪代码中各个变量的含义与范围如下:

∙ \hspace{23pt}\bullet\,nn:护符数量,1≦n≦1051 \leqq n \leqq 10^5;

∙ \hspace{23pt}\bullet\,mm:操作次数,1≦m≦1051 \leqq m \leqq 10^5;

∙ \hspace{23pt}\bullet\,seed\mathrm{seed}:随机种子,0≦seed<109+70 \leqq \mathrm{seed} \lt 10^9+7。每次调用 rnd()\mathrm{rnd}() 都会先返回当前的 seed\mathrm{seed},再将 seed\mathrm{seed} 更新为 $(\mathrm{seed} \times 7+13) \bmod \left(10^9+7\right)$;

∙ \hspace{23pt}\bullet\,vmax\mathrm{vmax}:数值上限,1≦vmax≦1091 \leqq \mathrm{vmax} \leqq 10^9。初始值 aia_i、类型 11 和类型 22 的 xx、类型 44 的 yy 都在 [1,vmax]\left[1,\mathrm{vmax}\right] 内。

\hspace{15pt}伪代码依次生成 a1,a2,…,ana_1,a_2,\dots,a_n,随后依次生成 mm 次操作的 op,l,r,x\mathrm{op},l,r,x;当 op=4\mathrm{op}=4 时还会额外生成 yy。生成的 l,rl,r 满足 1≦l≦r≦n1 \leqq l \leqq r \leqq n。

输出格式

\hspace{15pt}对于每一次类型为 33 或 44 的操作,新起一行输出一个整数,代表该次操作的答案。类型为 11 或 22 的操作不会产生输出。

测试样例

10 10 7 9
2
1
0
3

样例 1 解释

\hspace{15pt}按照伪代码生成,初始数组为 {8,9,7,2,3,1,5,6,4,8}\{8,9,7,2,3,1,5,6,4,8\},1010 次操作依次为:

∙ \hspace{23pt}\bullet\,类型 22:l=6,r=7,x=9l=6,r=7,x=9;

∙ \hspace{23pt}\bullet\,类型 11:l=3,r=10,x=8l=3,r=10,x=8;

∙ \hspace{23pt}\bullet\,类型 44:l=4,r=6,x=2,y=4l=4,r=6,x=2,y=4;

∙ \hspace{23pt}\bullet\,类型 11:l=4,r=5,x=8l=4,r=5,x=8;

∙ \hspace{23pt}\bullet\,类型 22:l=1,r=7,x=1l=1,r=7,x=1;

∙ \hspace{23pt}\bullet\,类型 44:l=7,r=9,x=4,y=4l=7,r=9,x=4,y=4;

∙ \hspace{23pt}\bullet\,类型 11:l=2,r=7,x=9l=2,r=7,x=9;

∙ \hspace{23pt}\bullet\,类型 44:l=5,r=8,x=1,y=1l=5,r=8,x=1,y=1;

∙ \hspace{23pt}\bullet\,类型 22:l=5,r=7,x=5l=5,r=7,x=5;

∙ \hspace{23pt}\bullet\,类型 44:l=3,r=10,x=8,y=5l=3,r=10,x=8,y=5。

\hspace{15pt}其中第 3,6,8,103,6,8,10 次操作都是类型 44,输出的答案依次为 2,1,0,32,1,0,3。

10 10 9 9
1
1
3
3