scu 3139単調キュー

リンク:http://acm.scu.edu.cn/soj/problem.action?id=3139 単調キューの古典的な応用.标题:長さnのスライド窓があり、スライド窓を右にまっすぐ移動し、このスライド窓の最大値の最小値がどれだけあるかを決定します.単調キュー:両端キューとも呼ばれます.最大値の保存を例にとります.キュー内の要素は単調で減らない.キューヘッダには最大値が格納され、要素をキューに追加するたびに、キューの最後からこの要素よりも小さなポップアップが表示され、最後にこの要素がキューに追加されます.キューの要素がスライド窓の外にあるかどうかを判断するたびに、いるとポップアップします.キュー内の各要素は、元の配列のインデックスと独自の値を保存できます.スライド窓内にあるかどうかを判断するのに便利です.もちろんインデックスだけを保存して、元の配列で探せばいいのです.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000009
typedef struct
{
    int index;
    int num;
}node;
node que1[M],que2[M]; //1     ，2     
int ans1[M],ans2[M];
int main()
{
    //freopen("ans.txt","r",stdin);
    int n,k;
    while(scanf("%d %d",&n,&k) == 2)
    {
        int head1 = 0,tail1 = 0;
        int head2 = 0,tail2 = 0;
        for(int i = 0;i < n;i++)
        {
            int a;
            scanf("%d",&a);
            while(head1 != tail1 && que1[tail1-1].num > a) tail1--; //              ，      
            que1[tail1++] = {i,a};
            if(que1[head1].index <= i-k) head1++;
            while(head2 != tail2 && que2[tail2-1].num < a) tail2--;
            que2[tail2++] = {i,a};
            if(que2[head2].index <= i-k) head2++;
            if(i >= k-1)
            {
                ans1[i-k+1] = que1[head1].num;
                ans2[i-k+1] = que2[head2].num;
            }
        }
        for(int i = 0;i <= n-k;i++) printf("%d%c",ans1[i],i==n-k ? '
':' ');
        for(int i = 0;i <= n-k;i++) printf("%d%c",ans2[i],i==n-k ? '
':' ');
    }
    return 0;
}