chen_zhe
2022-09-05 21:18:22
双端队列是一种可以在队首和队尾插入或者弹出的一种数据结构。在 C++ 的 STL 中提供了 std::deque 这一容器可以维护一个双端队列。其运用方式如下：
| 用法 | 含义 |
|---|---|
q.push_back(x) |
在双端队列末尾插入元素 |
q.pop_back() |
在双端队列末尾弹出元素 |
q.push_front(x) |
在双端队列头部插入元素 |
q.pop_front() |
在双端队列开头弹出元素 |
q.size() |
查询双端队列元素个数 |
q.front() |
返回双端队列队首 |
q.back() |
返回双端队列队尾 |
根据这一容器我们当然可以快速地实现本题，但是 std::deque 的实现是很慢的，有着很大的空间常数。如果直接开 std::deque <int> q[1000050]，其将占据 650 MB 左右的内存，这将直接导致 MLE，而且在本题的输入规模与 std::deque 的效率下，哪怕给予足够多内存空间也将 TLE。根据 cppreference 的说明，std::deque 的实现会预先分配固定大小的数组，这是内存占用的大头。此外 deque 存储元素也要用较大的内存，一个只包含一个元素的 std::deque 也将会占用其变量类型 std::deque 的极大的空间占用。此外，由于 std::queue() 和 std::stack() 也是依赖于 std::deque 的，因此在使用它们的时候也应当要注意。
如果不要求支持随机访问队列下标，那么 std::deque 可以用 std::list 代替，也就是本题了。需要注意 std::list 的连续访问效率较低。