你可以用priority_queue逝一下
by Xrange @ 2024-05-12 15:52:21
@[Xrange](/user/1255916) 这题考的单调队列,不是优先队列吧
by masonxiong @ 2024-05-12 15:53:57
@[masonxiong](/user/446979) 那deque???
by Xrange @ 2024-05-12 16:10:58
## AC部分代码:
deque的定义:
```cpp
struct ty { int id,val; }a[2000100];
long long n,m,sq[2000100];
```
deque的主要部分:
```cpp
for(int i=1;i<=n;i++) {
while(!q.empty()&&q.back().val>=a[i].val)
q.pop_back();
q.push_back(a[i]);
while(!q.empty()&&q.front().id<i-m)
q.pop_front();
sq[i]=q.front().val;
}
```
@[wfirstzhang](/user/1312537) @masionxiong
by Xrange @ 2024-05-12 16:46:52
@[Xrange](/user/1255916)
同志,你似乎对双端队列,优先队列和单调队列有一些误解
所谓“优先队列”,即 `std::priority_queue`,可以 $O(\log n)$ 维护数列最值
所谓“双端队列”,即 `std::deque`,维护一个序列,支持随机访问和 $O(1)$ 的首尾增删
所谓“单调队列”,即 `monotonous_queue`,这个并没有在 STL 中,它是一种 OI 中常用(?)的数据结构,也是本题考查的部分,就是你写的那些
by masonxiong @ 2024-05-12 17:47:07
@[masonxiong](/user/446979) 抱歉我是xxs
by Xrange @ 2024-05-12 17:53:25
我说**用 ```deque``` 实现**没说**思想是 ```deque```** !!!
by Xrange @ 2024-05-12 20:17:06
@[Xrange](/user/1255916) @[masonxiong](/user/446979) 找到问题了,原来写成 $tail \ge front$ 了,改成 $tail > front$,问题解决。
by wfirstzhang @ 2024-05-12 21:44:11
@[wfirstzhang](/user/1312537) 这和 ```!q.empty()``` 等价
by Xrange @ 2024-05-13 16:48:29