绫小路的特别考试

ID: 3940

远端评测题

3000ms

250MiB

尝试: 0

已通过: 0

难度: 6

上传者:

root

标签>

贪心

枚举,暴力

排序

深度优先搜索,DFS

栈

题目背景

这世界上「胜利」便是一切。无关乎过程。要付出多少牺牲都无所谓。只要最后我「胜出」那就行了。

题目描述

一场新的特别考试来临了，这次的考试内容是（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$ 。

若一名同学的对讲机接收范围被调整多次，以最后一次为准。

** 数据生成器模板：**

#include <cstdio>

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$ 。

3 3 2
19720918 0 1 2 0

10 10 8
2102036 0 1 4 1
5 2

760521825

1000 1000 126
114321251 1 2 2 0

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<n$ 。

其它用于生成数据的变量：

$1\le \mathrm{seed},\ \mathrm{mfq}\le 10^9$ ， $0\le \mathrm{mind}\le \mathrm{maxd}<n$ ， $0\le k\le 2\times 10^5$ ， $1\le p\le n$ ， $0\le t<n$ 。

样例解释

样例一：

生成得到三名同学的能力值 $w_{1..3} = \{0,\ 1,\ 2\}$ ，对讲机接收范围 $d_{1..3} = \{1,\ 0,\ 1\}$ 。

第一个操作是 1 1，询问有多少同学会做难度为 $1$ 的题。

绫小路（第 $2$ 名同学）和第 $3$ 名同学能够独立做出这道题（ $w_2 \ge 1$ ， $w_3 \ge 1$ ），第 $1$ 名同学虽然能力不足，但通过对讲机能接收到绫小路广播的做法（ $2 \in [1 - d_1,\ 1 + d_1]$ ），所以他也会做。故 $ans_1 = 3$ 。

第二个操作是 2 0，修改绫小路（第 $2$ 名同学）的能力值为 $0$ 。此时 $w_{1..3} = \{0,\ 0,\ 2\}$ 。

第三个操作是 1 1，再次询问有多少同学会做难度为 $1$ 的题。

只有第 $3$ 名同学能够独立做出（ $w_3 \ge 1$ ），然而第 $1$ 名同学和绫小路（第 $2$ 名同学）都无法接收到他广播的做法（ $3 \notin [1 - d_1,\ 1 + d_1]$ ， $3 \notin [2 - d_2,\ 2 + d_2]$ ），做不出来。故 $ans_2 = 1$ 。

综上所述， $T_1 = ans_1 = 3$ ， $T_2 = 3 \times T_1+ ans_2 = 3 \times 233 + 1 = 700$ ，仅输出 $700$ 即可。

样例二：

生成得到 $w_{1..10} = \{1,\ 6,\ 6,\ 5,\ 3,\ 5,\ 2,\ 7,\ 9,\ 5\}$，$d_{1..10} =\{1,\ 1,\ 1,\ 1,\ 2,\ 0,\ 1,\ 0,\ 1,\ 1\}$。

十次操作及对应结果如下所示：

1 6，查询操作， $ans_1 = 9$ ， $T_1 = 9$ 。

2 2，修改操作， $w_{1..10}$ 变为 $\{1,\ 6,\ 6,\ 5,\ 3,\ 5,\ 2,\ 2,\ 9,\ 5\}$ 。

1 7，查询操作， $ans_2 = 2$ ， $T_2 = 2099$ 。

1 3，查询操作， $ans_3 = 9$ ， $T_3 = 489076$ 。

2 4，修改操作， $w_{1..10}$ 变为 $\{1,\ 6,\ 6,\ 5,\ 3,\ 5,\ 2,\ 4,\ 9,\ 5\}$ 。

1 3，查询操作， $ans_4 = 10$ ， $T_4 = 113954718$ 。

2 2，修改操作， $w_{1..10}$ 变为 $\{1,\ 6,\ 6,\ 5,\ 3,\ 5,\ 2,\ 2,\ 9,\ 5\}$ 。

1 9，查询操作， $ans_5 = 2$ ， $T_5 = 597096118$ 。

1 0，查询操作， $ans_6 = 10$ ， $T_6 = 367430437$ 。

1 3，查询操作， $ans_7 = 9$ ， $T_7 = 760521825$ 。

仅输出 $760521825$ 即可。

样例三：

~~出题人有足够的良心写出这个样例的解释，可惜版面太小，写不下。~~

#P4964. 绫小路的特别考试