P7908 [Ynoi2005] qwq

Define the initial sequence as a sequence in which every number is $0$. Define one operation as increasing the value of every number in an interval of the sequence by $1$, with the restriction that the length of this interval cannot exceed $m$. Given a sequence $a$ of length $n$, where the $i$-th number is $a_i$. You need to answer $q$ queries. In each query, you are given $l, r$, and you need to output the minimum number of operations required to turn an initial sequence of length $r-l+1$ into the subarray $[l, r]$ of $a$ (that is, the sequence $a_l, a_{l+1}, \cdots, a_r$).

The first line contains three integers $n, m, q$. The second line contains $n$ integers, where the $i$-th is $a_i$. The next $q$ lines each contain two integers $l, r$.

Output $q$ lines, each containing one integer, indicating the minimum number of operations.

**"Sample 1 Explanation"** An initial sequence of length $5$ is $0$ $0$ $0$ $0$ $0$. In the first operation, increase every number in the interval $[1,3]$, that is, the $1$st, $2$nd, and $3$rd numbers, by $1$. After this operation, the sequence becomes $1$ $1$ $1$ $0$ $0$. In the second operation, increase every number in the interval $[3,5]$, that is, the $3$rd, $4$th, and $5$th numbers, by $1$. After this operation, the sequence becomes $1$ $1$ $2$ $1$ $1$. **"Constraints and Notes"** - Subtask 1 (1 point): $m=1$. - Subtask 2 (4 points): $m=n$. - Subtask 3 (10 points): $n,q\le300$. - Subtask 4 (10 points): $n,q\le5\times10^3$. - Subtask 5 (15 points): $m\le5$. - Subtask 6 (15 points): $m\le100$. - Subtask 7 (20 points): $n,q\le5\times10^4$. - Subtask 8 (25 points): no special constraints. For $100\%$ of the testdata, it is guaranteed that $1\le m\le n\le10^5$, $1\le q\le10^5$, $0\le a_i\le10^9$, and $1\le l\le r\le n$. Translated by ChatGPT 5