【题意】 n个数，现在有一个大小为w的划窗，窗口每个时刻向后移动一位，求出每个时刻窗口中数字的最大值和最小值。

【解题方法】

求最大值：建立一个单调递减队列，元素从左到右依次入队，入队之前必须从队列尾部开始删除那些比当前入队元素小或者相等的元素，直到遇到一个比当前入队元素大的元素，或者队列为空为止。若此时队列的大小超过窗口值，则从队头删除元素，直到队列大小小入窗口值为止。然后把当前元素插入队尾。

求最小值：建立一个单调递增队列，元素从左到右依次入队，入队之前必须从队列发问开始删除那些比当前入队元素大或者相等的元素，直到遇到一个比当前入队元素小的元素，或者队列为空为止。若此时队列的大小超过窗口值，则从队头删除元素，直到队列大小小入窗口值为止。然后把当前元素插入队尾。

设窗口大小为k，本题解法为建立两个单调队列，先从原数组中取前k个元素按上述要求入队，然后获取队头元素，再把下一个元素放入队中，再获取头元素，这样一直到最后一个元素为止。最后把答案从头到尾依次输出即可。

我只能说我的单调队列，跑了5000+ms,真是吓尿，还是c++过的，g++直接t了，不知道这个是什么说法，具体看代码吧。


【代码君】


//
//Created by just_sort 2016/1/6
//Copyright (c) 2016 just_sort.All Rights Reserved
//

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 1000010;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
//const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
struct node{
    int v, pos;
    node(){}
    node(int v, int pos) : v(v), pos(pos) {}
}que1[maxn], que2[maxn];
int ans1[maxn], ans2[maxn], head1, tail1, head2, tail2, cnt;

int main()
{
    int n, w;
    scanf("%d%d", &n, &w);
    head1 = tail1 = head2 = tail2 = cnt = 0;
    REP1(i, 0, w){
        int x;
        scanf("%d", &x);
        //维护单调递减队列，队首元素为最大值
        while(head1 < tail1 && que1[tail1 - 1].v >= x) --tail1;
        que1[tail1] = node(x, i);
        ++tail1;
        //维护单调递增队列，队首元素为最小值
        while(head2 < tail2 && que2[tail2 - 1].v <= x) -- tail2;
        que2[tail2] = node(x, i);
        ++tail2;
    }
    REP1(i, w, n){
        ans1[cnt] = que1[head1].v;
        ans2[cnt] = que2[head2].v;
        ++cnt;
        int x;
        scanf("%d", &x);
        //保证维护的单调队列大小不超过k
        while(head1 < tail1 && i - que1[head1].pos >= w) ++head1;
        while(head1 < tail1 && que1[tail1 - 1].v >= x) --tail1;
        que1[tail1] = node(x, i);
        ++tail1;
        //同上
        while(head2 < tail2 && i - que2[head2].pos >= w) ++head2;
        while(head2 < tail2 && que2[tail2 - 1].v <= x) --tail2;
        que2[tail2] = node(x, i);
        ++tail2;
    }
    ans1[cnt] = que1[head1].v;
    ans2[cnt] = que2[head2].v;
    ++cnt;
    REP1(i, 0, cnt){
        printf("%d%c", ans1[i], (i == (cnt - 1)) ? '\n' : ' ');
    }
    REP1(i, 0, cnt){
        printf("%d%c", ans2[i], (i == (cnt - 1)) ? '\n' : ' ');
    }
    return 0;
}