#3#4#7 WA

P1440 求m区间内的最小值

你可以用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


|