P15133 [ROIR 2026] The Last Sliding Window Problem

Consider a numeric array $b_1, \dots, b_m$. A sliding window of length $k$ ($k \le m$) on this array refers to all subsegments of length $k$, i.e. $\{b_1, \dots, b_k\}$, $\{b_2, \dots, b_{k + 1}\}$, $\dots$, $\{b_{m-k+1}, \dots, b_m\}$. Given a numeric array $a_1, \dots, a_n$ of length $n$, answer $q$ queries about this array. Each query is as follows: for given $l$, $r$, and $k$, find the sum of the minimum values of all sliding windows of length $k$ on the subsegment $\{a_l, \dots, a_r\}$.

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$), the length of the array and the number of queries. The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$), the values in the array. The next $q$ lines describe the queries. The $i$-th line contains three integers $l_i$, $r_i$, and $k_i$ ($1 \le l \le r \le n$, $1 \le k \le r - l + 1$), the left and right boundaries of the subsegment and the sliding window length for the $i$-th query.

Output $q$ lines, each containing the answer to the corresponding query. On the $i$-th line, output one number, the sum of the minimum values of all sliding windows of length $k_i$ on the subsegment $\{a_{l_i}, \dots, a_{r_i}\}$.

| Subtask | Score | Additional Constraints | Dependencies | |:-:|:-:|:-:|:-:| | 1 | 6 | $n, q \le 300$ | | | 2 | 12 | $n, q \le 4000$ | 1 | | 3 | 8 | $n, q \le 10\,000$ | 1–2 | | 4 | 11 | $n \le 4\,000$ | 1–2 | | 5 | 10 | All queries have the same $k_i$ | | | 6 | 14 | $a_i \le 2$ | | | 7 | 7 | $a_i \le 20$ | 6 | | 8 | 15 | $l_i = 1, r_i = n$ | | | 9 | 17 | No additional constraints | 1–8 | Translated by ChatGPT 5