题解 P1886 【滑动窗口】

这道题是单调队列的模版题，一看数据1000000，就知道暴力DP是九死一生 下面讲讲什么是单调队列，知道的dalao请跳过 ------------ 单调队列分为单调递增和单调递减两种，我们只需要维护这个单调队列，怎么维护？ 1. 以递增序列为例 插入：如果将要插入的元素x>队尾元素，x直接入队，若x<=队尾元素，则弹出队尾元素，直到x>队尾元素 访问：如果要想得到小元素，直接访问队首元素即可 ------------ 而这道题，我们只需要维护**一个单调递增队列和一个单调递减队列**，同时判断队首元素是否合法（即其是否在区间内），再用一个ans数组来记录答案，特别注意最左端是从k开始，因为区间不能越界 ------------ 接下来上代码，建议不要照这些，先想一下，实在想不出来再看 **~~好吧，太啰嗦了~~** ```cpp #include<iostream> #include<cstdio> using namespace std; int q1[1000005],q2[1000005],l1,l2,r1,r2,n,k,a[1000005],ans1[1000005],ans2[1000005]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) { while(q1[l1]<i-k+1&&l1<=r1)l1++; while(a[q1[r1]]>a[i]&&r1>=l1)r1--; q1[++r1]=i; ans1[i]=a[q1[l1]]; while(q2[l2]<i-k+1&&r2>=l2) l2++; while(a[q2[r2]]<a[i]&&r2>=l2) r2--; q2[++r2]=i; ans2[i]=a[q2[l2]]; } for(int i=k;i<=n;i++) printf("%d ",ans1[i]); printf("\n"); for(int i=k;i<=n;i++) printf("%d ",ans2[i]); } ``` ------------