自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 21:59:29，当前版本为作者最后更新于2023-08-27 08:35:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

函数式（grader 式）交互题．

给定整数 $n,k$（$1 \le k \le n \le 10^6$）．你需要实现函数 void helpBessie(int x)．一个长度为 $n$ 的数组 $a$ 将会被遍历两次，每遍历到一个元素时会将其作为参数调用一次 helpBessie．

给定汇报函数 void shoutMinimum(int x)．你需要在整个程序内调用该函数恰好 $n-k+1$ 次．第 $i$ 次时需要传入 $\min_{j=i}^{i+k-1} a_j$ 作为参数．只有调用次数为 $n-k+1$ 次且每次调用汇报答案均正确时，测试点才会返回 Accepted 评测结果．

交互库提供了 $5500$ 个 $32$ 位有符号整数寄存器．寄存器在整个程序中最多可以被读或写 $2.5 \cdot 10^7$ 次．寄存器中的整数可以在两次调用 helpBessie 之间传递．除此之外，其他保存在静态或全局变量中的信息不可以在下次调用时读出．

算法简述

为方便表述，我们认为 $a$ 数组的下标从 $1$ 开始．

我们设 $f_i = \arg\min_{j=i}^{i+k-1} a_j$，如果有多个最小值点则 $f_i$ 取最小的．根据滑动窗口的性质，若 $x < y$，有 $f_x \leq f_y$．

这启发我们将序列分块．设块长为 $B$，则第 $i$ 个块左端点为 $(i-1)B+1$，右端点为 $iB$．若 $(i-1)B < j < i B$，则一定有 $f_{(i-1)B+1} \le f_j \le f_{i B}$．以当前块和下一块的左端点的 $f$ 值求出当前块中其他位置的 $f$ 值，进而求出最终答案．

考虑如何求 $f$，常见的方法是单调队列，但本题由于具有全局空间限制而无法使用．另一种方式是采用数据结构维护区间最小值和最小值下标，由于本题对全局空间的限制，使用分块维护是一个比较好的选择．我们在第一次遍历 $a$ 数组的时候维护目前扫过的所有整块和右散块的最小值和最小值下标，则可以在扫描至 $((i-1)B+1) + k - 1$ 时求出 $f_{(i-1)B+1}$．

在第二次遍历时，我们需要对块中的非左端点元素求出 $f_i$．我们逐块考虑，设目前处理的是第 $i$ 块．若不考虑全局空间限制，存在一个使用双端单调队列的方法：维护一个类型为（下标，值）二元组，且按照值从左到右严格递增的双端单调队列．遍历 $a$ 的 $[f_{(i-1)B+1}, f_{iB}]$ 子区间．遍历到下标 $p$ 时将 $(p,a_p)$ 加入队列右端．加入下标为 $p$ 的元素前将队列左侧所有下标小于 $p-k+1$ 的元素删除．加入下标为 $p$ 的元素后，如果下标 $p-k+1$ 是当前块的非左端点，则以双端单调队列最左侧元素的值汇报 $p-k+1$ 处的答案．如果加入 $f_{iB}$ 后仍然有块内位置没有被汇报答案，则以双端单调队列最左侧元素的值汇报剩余位置的答案．

接下来考虑全局空间限制．观察到如果我们给双端队列设置一个最大长度 $L$，在即将在右端加入元素时，若当前队列元素个数已经为 $L$，则不加入．当取 $L=B+O(1)$ 时，不会影响最终的答案．对此有一个简单的证明：我们将 $[f_{(i-1)B+1}, f_{iB}]$ 的下标按照 $\leq iB + k - 1$ 和 $> iB + k - 1$ 分为两部分．第一部分最多包含 $B$ 个下标，这些下标一定能成功加入双端队列，故如果答案来自这一部分则不会受到影响．对于第二部分，属于这一部分的下标一旦被加入双端队列就不可能从左侧弹出，只能从右侧弹出，也就是说若这一部分中的一个下标 $p$ 成为了某个位置的 $f$ 值，则在 $p$ 对应的元素加入双端队列前，一定会先 pop 掉所有下标 $> iB + k - 1$ 的元素，此时双端队列内的元素个数一定 $\leq B$，故 $p$ 一定能成功加入双端队列．

这个做法的时间复杂度为 $O(n + (\frac{n}{B})^2)$，空间复杂度为 $O(B + \frac n B)$．当 $B = O(\sqrt n)$ 时，时间复杂度为 $O(n)$，空间复杂度为 $O(\sqrt n)$．可以通过本题．

代码参考

见 原始 OJ 提交．