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 数有多少这样的区间。

无

无

**【样例解释 $\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$。