MinMax

输入描述:

输入的第一行是两个整数n k。
接下来一行n个整数，表示数列a_i

输出描述:

输出两行，每行n-k+1个数，第一行是b数组，第二行是c数组。

示例1
输入

8 3
1 3 -1 -3 5 3 6 7

输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明

n<=10^6

minmax.cppview raw

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1000010;
int a[N];

int q[N];
int ans[N];
int tt=0, rr = -1;

int n, k;

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(tt<=rr && a[q[rr]]>=a[i]) rr--;
        q[++rr] = i;
        while(tt<=rr && i-q[tt]>=k) tt++;
        ans[i] = q[tt];
    }

    for(int i=k;i<=n;i++) printf("%d ", a[ans[i]]);
    puts("");

    tt =0, rr = -1;
    for(int i=1;i<=n;i++){
        while(tt<=rr && a[q[rr]]<=a[i]) rr--;
        q[++rr] = i;
        while(tt<=rr && i-q[tt]>=k) tt++;
        ans[i] = q[tt];
    }

    for(int i=k;i<=n;i++) printf("%d ", a[ans[i]]);
    puts("");
    return 0;
}