POJ 2823 Sliding Window

单调队列模板题。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000050
using namespace std;
int n,k,num[maxn],ans1[maxn],ans2[maxn];
int q1[maxn],q2[maxn],l1=1,l2=1,r1,r2;
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&num[i]);
for (int i=1;i<=n;i++)
{
while((l1<=r1) && (q1[l1]<=i-k)) l1++;
while((l2<=r2) && (q2[l2]<=i-k)) l2++;
while ((l1<=r1) && (num[i]<num[q1[r1]])) r1--;
q1[++r1]=i;
while ((l2<=r2) && (num[i]>num[q2[r2]])) r2--;
q2[++r2]=i;
ans1[i]=num[q1[l1]];
ans2[i]=num[q2[l2]];
}
for (int i=k;i<=n;i++) printf("%d ",ans1[i]);
printf(" ");
for (int i=k;i<=n;i++) printf("%d ",ans2[i]);
return 0;
}