绫小路的特别考试

题目背景

> 这世界上「胜利」便是一切。无关乎过程。 要付出多少牺牲都无所谓。只要最后我「胜出」那就行了。 ![](https://i.loli.net/2018/10/06/5bb879f4ac370.jpg)

题目描述

一场新的特别考试来临了,这次的考试内容是(wan e de)文化课,但有所不同的是,考试中允许学生使用对讲机。然而,对讲机的接收范围是有限的(每个对讲机都能发送无限远,但是只能接收到接收范围内的信号),所以不是所有学生都能接收到其他同学的广播。 考试时,共有 $n$ 名学生坐成一排(从左至右依次编号为 $1$ ~ $n$),绫小路自己坐在第 $c$ 号位置。每名学生都有一个能力值 $w_i$。绫小路已经给每名学生安排了一个接收范围为 $d_i$ 的对讲机。 每名学生可以直接做出难度**不超过**自身能力值的**所有**题目,一旦一名学生凭能力做出某道题,他就会把这道题的做法进行广播。一名坐在位置 $i$,有接收范围为 $d_i$ 的对讲机的学生,可以接收到 $[i-d_i,\ i+d_i]$ 范围内所有学生的广播,若这个范围内有人公布了做法,则他将会做这道题,并也会把这道题的做法进行广播。 绫小路会问你一些问题:当一道题目难度为 $x$ 时,有多少学生会做这道题?由于绫小路想隐藏实力,他可能会修改自己的能力值。这两种操作分别用以下两种方式表示: - $1\ x$,表示询问当一道题目难度为 $x$ 时,有多少学生会做这道题。 - $2\ x$,将绫小路的能力值修改为 $x$,即将 $w_c$ 修改为 $x$。 --- 形式化描述(与上文同义): > 给你两个长为 $n$ 的数列 $w_{1..n}$ 和 $d_{1..n}$,以及一个 $w_c$ 可修改的位置 $c$。现在有两种操作(共 $m$ 次): - $1\ x$ 表示一次询问:设 $f_i=\begin{cases}1\quad(w_i\ge x)\\1\quad(\exists\ j \in [i - d_i,\ i + d_i],\ f_j=1)\\ 0\quad(otherwise)\end{cases}$,这里的 $f_i$ 定义中引用了 $f_j$,$\ \ \ \ $所以 $f_{1..n}$ 是会不断更新的,直到无法继续更新时,计算这次询问的答案为 $\sum\limits_{i=1}^nf_i$。 - $2\ x$ 表示一次修改:把 $w_c$ 修改为 $x$。

输入输出格式

输入格式


由于数据量太大,为了避免读入耗时过长,使用**伪随机数生成器**的方式输入,并**强制在线**。 **建议你忽略输入格式,直接使用下面提供的数据生成器模板,了解具体的生成过程对你来说是不必要的。** 第一行,三个正整数 $n,\ m,\ c$,分别代表学生的总人数,操作总数和绫小路所在的位置。 第二行,五个整数 $\mathrm{seed},\ \mathrm{mind},\ \mathrm{maxd},\ \mathrm{mfq},\ k$。 > 此处的 $\mathrm{mind},\ \mathrm{maxd}$ 仅用于生成初始的 $d_{1..n}$,下文中调整 $d_p$ 所用的 $t$ 可能不在 $[\mathrm{mind},\ \mathrm{maxd}]$ 范围内。 接下来的 $k$ 行,每行两个整数 $p,\ t$,表示调整第 $p$ 号同学的对讲机接收范围(即 $d_p$)为 $t$。 > 若一名同学的对讲机接收范围被调整多次,以**最后一次**为准。 --- ** 数据生成器模板:** ```cpp #include unsigned long long seed; int n, m, c, mfq, mind, maxd, k, w[2000001], d[2000001]; inline int randInt() { seed = 99999989 * seed + 1000000007; return seed >> 33; } void generate() { // 在读入种子后生成初始的 w 数组和 d 数组. for (int i = 1; i <= n; i++) { w[i] = randInt() % n; } for (int i = 1; i <= n; i++) { d[i] = randInt() % (maxd - mind + 1) + mind; } } void getOperation(int lastans, int &opt, int &x) { // 生成一次操作的参数 opt 和 x, lastans 表示上一次询问的答案, 初始值为 0. if ((0ll + randInt() + lastans) % mfq) { opt = 1; } else { opt = 2; } x = (0ll + randInt() + lastans) % n; } int main() { scanf("%d %d %d", &n, &m, &c); scanf("%llu %d %d %d %d", &seed, &mind, &maxd, &mfq, &k); generate(); for (int i = 1; i <= k; i++) { int p, t; scanf("%d %d", &p, &t); d[p] = t; } // 从这里开始,你可以使用生成的 w 数组和 d 数组. int lastans = 0, finalans = 0; for (int i = 1; i <= m; i++) { int opt, x; getOperation(lastans, opt, x); if (opt == 1) { // 在这里执行询问操作,并用答案的表达式替代下面的 ___. finalans = (finalans * 233ll + ___) % 998244353; lastans = ___; } else { // 在这里执行修改操作. } } printf("%d\n", finalans); return 0; } ```

输出格式


令 $ans_i$ 表示第 $i$ 次询问(操作 $1$)的答案,$T_i=\begin{cases}(T_{i-1}\times 233+ans_i)\mod 998244353\quad(i\ge 1)\\0\quad(i=0)\end{cases}$ 设 $q$ 表示询问(操作 $1$)的个数,你只需要输出一个整数 $T_q$。

输入输出样例

输入样例 #1

3 3 2
19720918 0 1 2 0

输出样例 #1

700

输入样例 #2

10 10 8
2102036 0 1 4 1
5 2

输出样例 #2

760521825

输入样例 #3

1000 1000 126
114321251 1 2 2 0

输出样例 #3

91977056

说明

### 你需要用到的变量: $1\le c\le n\le 2\times 10^6$,$1\le m\le 2\times 10^6$,$0\le w_i,\ d_i,\ x