CF896C Willem, Chtholly and Seniorious

题目描述

有 $n$ 个整数的序列 $a _ i$。

执行 $m$ 次操作。

有四种操作类型：

• $1\ l\ r\ x$ ：对于 $i$ 满足 $l \le i \le r$，将 $a _ i + x$ 赋值给 $a _ i$。
• $2\ l\ r\ x$ ：对于 $i$ 满足 $l \le i \le r$，将 $x$ 赋值给 $a _ i$。
• $3\ l\ r\ x$ ：输出范围 $[l, r]$ 中第 $x$ 小的数字，即在所有满足 $l \le i \le r$ 的 $a _ i$ 排序后第 $x$ 小的数字。保证 $1 \le x \le r - l + 1$。
• $4\ l\ r\ x\ y$ ：输出范围 $[l, r]$ 中所有 $a _ i$ 的 $x$ 次幂之和模 $y$，即 $\left( \sum _ {i = l} ^ r {a _ i} ^ x \right) \bmod y$。

输入格式

第一行包含四个整数 $n, m, seed, v _ {max}$（$1 \le n, m \le 10 ^ 5$，$0 \le seed < 10 ^ 9 + 7$，$1 \le v _ {max} \le 10 ^ 9$）。

初始值和操作通过如下伪代码生成：

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

这里的 $op$ 是题目中提到的操作类型。

输出格式

对于每个类型为 $3$ 或 $4$ 的操作，输出答案。

输入输出样例 #1

输入 #1

10 10 7 9

输出 #1

2
1
0
3

输入输出样例 #2

输入 #2

10 10 9 9

输出 #2

1
1
3
3

说明/提示

对于样例 1，初始数组为 $\{8,9,7,2,3,1,5,6,4,8\}$。

操作如下：

• $2\ 6\ 7\ 9$
• $1\ 3\ 10\ 8$
• $4\ 4\ 6\ 2\ 4$
• $1\ 4\ 5\ 8$
• $2\ 1\ 7\ 1$
• $4\ 7\ 9\ 4\ 4$
• $1\ 2\ 7\ 9$
• $4\ 5\ 8\ 1\ 1$
• $2\ 5\ 7\ 5$
• $4\ 3\ 10\ 8\ 5$