P11745 Dynamic K-th Problem

> Fireflies pass through the wind, melt into flying light, and bloom in your eyes.

Xiao D found a group of fireflies. There are $n$ fireflies in the group, arranged in a line in order and numbered from $1$ to $n$. Xiao D is very capable: at a glance he knows the brightness of these $n$ fireflies, and the brightness values form a permutation of $1\sim n$. Xiao D wants to pick some fireflies so that they can weave a dreamy, dazzling curtain of light. Specifically, he needs a **firefly interval**. Xiao D has strict requirements for a **firefly interval**: it must contain at least $k$ fireflies, and their indices must be consecutive. Xiao D greatly admires the light of the fireflies. He defines the overall brightness value of the firefly interval from index $L$ to $R$ as the $m$-th largest number among the brightness values of those fireflies. Xiao D is given $Q$ thresholds. Each threshold gives a number $x$. You need to find how many **firefly intervals** have an overall brightness value greater than or equal to $x$. Of course, there can be many such intervals, and you need to help Xiao D count them.

The first line contains five integers $n,k,m,B,cas$, where $B$ is a given constant, and $cas$ is the Subtask ID of the current test point. The second line contains $n$ integers $a_i$ separated by spaces, representing the brightness values of the $n$ fireflies. They are generated by the given code. The third line contains an integer $Q$, denoting the number of thresholds. The fourth line contains $Q$ integers separated by spaces, representing the threshold $x$ for each query, generated by the given code. **The input size of this problem is large. The input data can be generated by the following code:** [The full code can be viewed here](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

For each query threshold, you need to compute the number of corresponding firefly intervals. To avoid excessive output, please output the **xor sum** of the numbers of firefly intervals over the $Q$ queries. For specific operation explanations, please refer to the sample explanation.

**[Sample Explanation $\mathbf 1$]** The brightness values of the fireflies from $1$ to $n$ are: $5,4,2,3,1$. There are $6$ firefly intervals in total. We take the $2$-nd largest value in each interval; they are: * The fireflies with indices $1$ to $3$ are $[5,4,2]$, and the overall brightness value is $4$. * The fireflies with indices $2$ to $4$ are $[4,2,3]$, and the overall brightness value is $3$. * The fireflies with indices $3$ to $5$ are $[2,3,1]$, and the overall brightness value is $2$. * The fireflies with indices $1$ to $4$ are $[5,4,2,3]$, and the overall brightness value is $4$. * The fireflies with indices $2$ to $5$ are $[4,2,3,1]$, and the overall brightness value is $3$. * The fireflies with indices $1$ to $5$ are $[5,4,2,3,1]$, and the overall brightness value is $4$. There are $5$ queries. The thresholds are $2,2,2,0,2$, so the answers are $6,6,6,6,6$. The total xor value is $6$. **[Sample Explanation $\mathbf 2$]** The brightness values of the fireflies from $1$ to $n$ are: $3,1,4,2,5,6$. There are $5$ queries. The thresholds are $1,5,1,4,6$, and the answers are $10,4,10,7,0$. The total xor value is $3$. **[Sample Explanation $\mathbf 3$]** This testdata satisfies the constraints of `Subtask 4`. The detailed solution is not explained. Please pay attention to integer overflow issues. **[Sample Explanation $\mathbf 4$]** This testdata satisfies the constraints of `Subtask 5`. The detailed solution is not explained. **[Sample Explanation $\mathbf 5$]** This testdata satisfies the constraints of `Subtask 8`. The detailed solution is not explained. --- **[Constraints and Notes]** **This problem uses bundled subtask testing**. The input/output size is not very large, but please optimize constants. This problem automatically enables O2 optimization. * 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$. For all test points: $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$. Translated by ChatGPT 5