P11745 Dynamic K-th Problem

> 萤火穿过风 融化成飞光 就在你眼眸盛放

小 D 发现了一群萤虫，萤群中有 $n$ 个萤虫且按照顺序排成一行并将其从 $1$ 从 $n$ 编号。小 D 非常厉害，他一眼就看出这 $n$ 个萤虫的光度，且这些萤虫的亮度值是 $1\sim n$ 的一个排列。小 D 想找一些萤虫，让它们共同编织出如梦似幻的璀璨光幕，具体的，他需要一个 **萤虫区间**。 小 D 对 **萤虫区间** 定义苛刻：至少得有 $k$ 个萤虫且这些萤虫编号连续。 小 D 十分欣赏萤虫的光芒，他定义编号从 $L$ 到 $R$ 的萤虫区间的总体光度值为这些萤虫的光度值中的第 $m$ 大数。小 D 给定了 $Q$ 个指标，每个指标给定一个数 $x$，寻找一个 **萤虫区间** 使得这个区间的总体光度值大于等于 $x$。当然，这种区间是很多的，你需要帮小 D 数有多少这样的区间。

第一行五个整数 $n,k,m,B,cas$，其中 $B$ 是给定常数，$cas$ 是当前数据点所属的 Subtask 编号。 第二行空格隔开的 $n$ 个数字 $a_i$，表示 $n$ 个萤虫的光度值。用给定代码生成。 第三行一个整数 $Q$，表示给定指标个数。 第四行空格隔开的 $Q$ 个数字，表示每次询问的指标 $x$，用给定代码生成。 **本题输入量较大，输入数据可以用以下代码生成：**[在此可查看完整代码](https://www.luogu.com.cn/paste/izknxvwf)。 ```cpp // 请注意避免整形溢出 #define int long long const int N = 1e6 + 5, INF = 2147483647; int n, k, m, B, Q, x, a[N], cas; // myrand 为数据生成器 struct myrand { int A, B, P, x; myrand(int A, int B, int P, int x) { this->A = A; this->B = B; this->P = P; this->x = x; } int next() { return x = (A * x + B) % P; } }; int read_x(int x) { // 不同数据下的 x 不同 if (cas == 7) x = x % 2; else x = x % (n + 1); return x; } signed main() { cin >> n >> k >> m >> B >> cas >> Q; // B 是生成数据是给定常数。在此初始化数据生成器 myrand 参数 myrand rnd(16807, B, INF, 0); // 伪随机生成 a 序列 for (int i = 1; i

对于每一个询问指标，都需要求出对应萤虫区间个数。 为了避免输出过多，请输出 $Q$ 次查询中萤虫区间个数的 **异或和**。具体操作解释请参见样例解释。

**【样例解释 $\mathbf 1$】** 萤虫从 $1$ 到 $n$ 的光度值为：$5,4,2,3,1$。总共有 $6$ 个萤虫区间，要求区间第 $2$ 大值，分别是： * 编号 $1$ 至 $3$ 构成的萤虫为 $[5,4,2]$，总体光度值为 $4$。 * 编号 $2$ 至 $4$ 构成的萤虫为 $[4,2,3]$，总体光度值为 $3$。 * 编号 $3$ 至 $5$ 构成的萤虫为 $[2,3,1]$，总体光度值为 $2$。 * 编号 $1$ 至 $4$ 构成的萤虫为 $[5,4,2,3]$，总体光度值为 $4$。 * 编号 $2$ 至 $5$ 构成的萤虫为 $[4,2,3,1]$，总体光度值为 $3$。 * 编号 $1$ 至 $5$ 构成的萤虫为 $[5,4,2,3,1]$，总体光度值为 $4$。 共有 $5$ 次询问，询问指标分别是 $2,2,2,0,2$，则答案分别是：$6,6,6,6,6$。则总异或值为 $6$。 **【样例解释 $\mathbf 2$】** 萤虫从 $1$ 到 $n$ 的光度值为：$3,1,4,2,5,6$。 共有 $5$ 次询问，询问指标分别是 $1,5,1,4,6$，答案分别是：$10,4,10,7,0$。则总异或值为 $3$。 **【样例解释 $\mathbf 3$】** 该数据满足 `Subtask 4` 的限制。具体求解不做解释。请注意整形溢出相关问题。 **【样例解释 $\mathbf 4$】** 该数据满足 `Subtask 5` 的限制。具体求解不做解释。 **【样例解释 $\mathbf 5$】** 该数据满足 `Subtask 8` 的限制。具体求解不做解释。 --- **【数据规模与约定】** **本题开启子任务捆绑测试**。本题输入输出量一点不大，但请注意优化常数。本题自动开启 O2 优化。 * Subtask 1（10 pts）：$m\leq n\leq 100$，$Q\leq 100$。 * Subtask 2（10 pts）：$m\leq n\leq 1000$，$Q\leq 100$。 * Subtask 3（18 pts）：$n\leq 10^5$，$m\leq 100$。 * Subtask 4（9 pts）：$n\leq 10^6$，$m=1$。 * Subtask 5（9 pts）：$n\leq 10^6$，$m=2$。 * Subtask 6（15 pts）：$n\leq 10^6$，$k=m\leq 100$。 * Subtask 7（7 pts）：$n\leq 10^6$，$m\leq 100$，$0\leq x\leq 1$。 * Subtask 8（22 pts）：$n\leq 10^6$，$m\leq 100$。 对于所有测试点满足 $1\leq m\leq k\leq n\leq 10^6$，$m\leq \min\{1000,n\}$，$1\leq a_i\leq n$，$1\leq Q\leq 10^6$，$1\leq B\leq 10^9$。