单调队列是什么

今天在rq看了道题目
http://www.rqnoj.cn/Problem_Show.asp?PID=460
大牛说这题道题目要用单调队列
我在网上找也没找到
来这里请教一下
说详细一点

不要直接复制的
网上的我都看过了

谢谢了

至于 460 的单调队列，就我目前的看法，只能实现 O(NlgN) 的算法（嗯，之前写的所谓 O(N) 算法是有问题的，至少不太好实现）。

我大致说一下，从前往后枚举以每个元素结尾的符合要求的二元组个数，并且不断维护之前的数组。显然，在之前数组的任意位置都不应出现逆序对（逆序对的后一个元素显然是没有前途的）。删去所有逆序对之后得到的就是一个单调非增的序列。于是对于以当前元素结尾的二元组，在之前的队列中从第一个比当前元素大的元素开始直到结尾的所有元素都符合要求，可以二分查找出这个位置，这一步 O(lgN)。之后我们将当前元素插入队列，由于原先队列已经有序，所以只要将队头比当前元素小的删除即可，平摊复杂度 O(1)。

至于 O(N) 算法，后来想了一下，理论上来说插入队列时删去的元素个数（大多数情况下再加1）就是当前元素结尾的二元组个数。但是有一种情况，就是出现与当前元素相等的元素，这种元素不能删除，只能一个一个统计。所以每步操作复杂度就不是 O(1) 了。不过理论上可以再用一些东西标记以实现 O(1)，我没细想了。

从前往后枚举以每个元素结尾的符合要求的二元组个数，并且不断维护之前的数组。显然，在之前数组的任意位置都不应出现逆序对（逆序对的后一个元素显然是没有前途的）。删去所有逆序对之后得到的就是一个单调非增的序列。于是对于以当前元素结尾的二元组，在之前的队列中从第一个比当前元素大的元素开始直到结尾的所有元素都符合要求，可以二分查找出这个位置，这一步 o(lgn)。之后我们将当前元素插入队列，由于原先队列已经有序，所以只要将队头比当前元素小的删除即可，平摊复杂度 o(1)。 至于 o(n) 算法，后来想了一下，理论上来说插入队列时删去的元素个数（大多数情况下再加1）就是当前元素结尾的二元组个数。但是有一种情况，就是出现与当前元素相等的元素，这种元素不能删除，只能一个一个统计。所以每步操作复杂度就不是 o(1) 了。不过理论上可以再用一些东西标记以实现 o(1)，我没细想了。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息