自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:14:12，当前版本为作者最后更新于2022-09-05 21:18:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

双端队列是一种可以在队首和队尾插入或者弹出的一种数据结构。在 C++ 的 STL 中提供了 std::deque 这一容器可以维护一个双端队列。其运用方式如下：

根据这一容器我们当然可以快速地实现本题，但是 std::deque 的实现是很慢的，有着很大的空间常数。如果直接开 std::deque <int> q[1000050]，其将占据 650 MB 左右的内存，这将直接导致 MLE，而且在本题的输入规模与 std::deque 的效率下，哪怕给予足够多内存空间也将 TLE。根据 cppreference 的说明，std::deque 的实现会预先分配固定大小的数组，这是内存占用的大头。此外 deque 存储元素也要用较大的内存，一个只包含一个元素的 std::deque 也将会占用其变量类型 $16$ 倍或者 $4096$ 字节的内存。这也就会造成 std::deque 的极大的空间占用。此外，由于 std::queue() 和 std::stack() 也是依赖于 std::deque 的，因此在使用它们的时候也应当要注意。

如果不要求支持随机访问队列下标，那么 std::deque 可以用 std::list 代替，也就是本题了。需要注意 std::list 的连续访问效率较低。