复杂度都不对就洗洗睡吧
by SSerxhs @ 2019-01-18 21:53:03
单调队列题
by 周子衡 @ 2019-01-18 21:54:50
~~线段树~~
by Kevin_Wa @ 2019-01-18 21:56:49
暴力显然是$O(nm)$的
我们可以构造一个队列，保存所有可能成为正确答案的元素
顺序扫描每一个元素，可以发现：如果$i<j$而$a_i\geq a_j$，那么$a_i$在有生之年就肯定不是正确答案，就从队中踢出
每次如果最先进入队列的元素过期了，也把它踢出
可以发现，这个队列的元素单调递增，故称单调队列
我讲得可能不是很清楚，具体看题解和[日报](https://sweetlemon.blog.luogu.org/dan-diao-dui-lie)吧
可以用$STL$的$deque$
by 周子衡 @ 2019-01-18 22:00:48
时间复杂度$O(n)$
by 周子衡 @ 2019-01-18 22:01:15