看下面一个例题： 给定一个序列，求所有区间长度为L的区间的最大值和最小值。 n,m<=5000000 这个题有啥做法？ O(nlogn)的线段树 O(nlogn)的带删除优先队列（对顶堆） 还能再快一点吗？ O(n)-O(1)RMQ代替线段树 还能再好写一点吗？O(n)的滑动窗口 在队列中维护一个单调性，换而言之让这个队列始终保持里面的元素拥有单调递增/单调递减的属性。 也就是说，维护这L个元素的最大值/最小值即可。 考虑到每个元素最多被进出队1次，因此这是一个O(n)的算法
//wei daima #include<iostream> using namespace std; const int N=50000010; int q[N],l=1,r=1,a[N],mx,mn,inq[N],n,m; inline void ins(int x) { while(l<r&&q[r-1]<=a[x]) r--; q[r]=a[x];inq[r]=x;r++; } int getmax(int cur) { for(l<r;l++)if(cur-inq[l]<m) return q[l] ; } int main() { return 0; }转载于:https://www.cnblogs.com/tbdemons/p/11296902.html
