P8864 "KDOI-03" Sequence Transformation

You are given a $\tt01$ sequence $a$ of length $n$ and $q$ queries, with query parameter $k$. In each query, you are given $L, R$ with $1 \le L \le R \le n$. You may perform the following operation: + Choose an index $L < i \le R$. + Set $a_{i-1}$ to $a_{i-1} \oplus a_i$, and set $a_{i+1}$ to $a_{i+1} \oplus a_i$. If $i = n$, then $a_{i+1}$ is not changed. Here $\oplus$ denotes the bitwise XOR operation. Find the minimum number of operations needed so that there are **at most** $k$ $\tt1$'s in the interval $[L, R]$. The queries are independent, meaning that after each query, the sequence is reset to the initial sequence.

Read input from standard input. The first line contains three positive integers $n, k, q$. The second line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$. The next $q$ lines each contain two positive integers $L, R$, representing one query.

Write output to standard output. Output $q$ lines in total, each containing one integer, the answer for the corresponding query.

**[Sample 1 Explanation]** As shown in the figure, green represents $\tt0$ and red represents $\tt1$. The initial sequence is as follows:  For the 1st query, choose $i = 3$, and the sequence becomes:  For the 2nd query, choose $i = 2$, and the sequence becomes:  **[Sample 2 Explanation]** For the 1st query, since among $a_{12}, a_{13}, a_{14}, a_{15}$ there are only $2$ $\tt1$'s, no operation is needed. For the 6th query, you can choose $i = \{7, 8, 9, 10, 11, 12\}$ in order. **[Sample 3]** See `control/control3.in` and `control/control3.ans` in the contestant files. This sample satisfies the constraints of test points $7 \sim 10$. **[Sample 4]** See `control/control4.in` and `control/control4.ans` in the contestant files. This sample satisfies the constraints of test points $15 \sim 17$. **[Sample 5]** See `control/control5.in` and `control/control5.ans` in the contestant files. This sample satisfies the constraints of test points $18 \sim 21$. *** **[Constraints]** For $100\%$ of the testdata: $2 \le n \le 3~000$, $1 \le k \le \min(n, 1~000)$, $1 \le q \le 5 \times 10^5$, $0 \le a_i \le 1$. | Test Point ID | $n \le$ | $k \le$ | $q \le$ | Special Property | | :--: | :--: | :--: | :--: | :--: | | $1 \sim 3$ | $80$ | $50$ | $2~000$ | None | | $4 \sim 6$ | $400$ | $300$ | $1$ | $k$ is even | | $7 \sim 10$ | $400$ | $2$ | $10~000$ | None | | $11 \sim 14$ | $400$ | $300$ | $10~000$ | None | | $15 \sim 17$ | $3~000$ | $10$ | $5 \times 10^5$ | None | | $18 \sim 21$ | $3~000$ | $1~000$ | $5 \times 10^5$ | $k$ is even | | $22 \sim 25$ | $3~000$ | $1~000$ | $5 \times 10^5$ | None | Translated by ChatGPT 5