P15133 [ROIR 2026] 最后的滑动窗口问题

考虑一个数字数组 $b_1, \dots, b_m$。该数组上长度为 $k$（$k \le m$）的滑动窗口是指所有长度为 $k$ 的子段，即 $\{b_1, \dots, b_k\},$ $\{b_2, \dots, b_{k + 1}\},$ $\dots,$ $\{b_{m-k+1}, \dots, b_m\}$。 给定一个长度为 $n$ 的数字数组 $a_1, \dots, a_n$。回答关于该数组的 $q$ 个查询，查询形式如下：对于给定的 $l$、$r$、$k$，找出子段 $\{a_l, \dots, a_r\}$ 上所有长度为 $k$ 的滑动窗口的最小值之和。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 100\,000$）—— 数组的长度和查询的数量。 第二行包含 $n$ 个整数 $a_1, \dots, a_n$（$1 \le a_i \le 10^9$）—— 数组中数字的值。 接下来的 $q$ 行包含查询。第 $i$ 行给出三个整数 $l_i$、$r_i$ 和 $k_i$（$1 \le l \le r \le n$，$1 \le k \le r - l + 1$）—— 第 $i$ 个查询的子段左右边界以及滑动窗口的长度。

输出 $q$ 行，每行包含对应查询的答案。第 $i$ 行输出一个数字 —— 子段 $\{a_{l_i}, \dots, a_{r_i}\}$ 上所有长度为 $k_i$ 的滑动窗口的最小值之和。

| 子任务 | 分值 | 额外限制 | 依赖子任务 | |:-:|:-:|:-:|:-:| | 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 | 所有查询中的 $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 | 无额外限制 | 1–8 |