记录编号	561614	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	cb	是否通过	通过
代码语言	C++	运行时间	1.946 s
提交时间	2021-07-03 09:03:39	内存使用	130.13 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, k, a[MAXN], st1[MAXN][21], st2[MAXN][21];

void init () {
    for (int q = 1; q <= 20; ++q) {
        for (int w = 1; w + (1 << q - 1) <= n; ++w) {
            st1[w][q] = max (st1[w][q - 1], st1[w + (1 << q - 1)][q - 1]);
            st2[w][q] = min (st2[w][q - 1], st2[w + (1 << q - 1)][q - 1]);
        }
    }
    return ;
}

int RMQ_x (int l, int r) {
    int k = log (r - l + 1) / log (2.0);
    return max (st1[l][k], st1[r - (1 << k) + 1][k]);
}

int RMQ_n (int l, int r) {
    int k = log (r - l + 1) / log (2.0);
    return min (st2[l][k], st2[r - (1 << k) + 1][k]);
}

int main () {
    freopen ("window.in", "r", stdin);
    freopen ("window.out", "w", stdout);
    scanf ("%d %d", &n, &k);
    for (int q = 1; q <= n; ++q) {
        scanf ("%d", &a[q]);
        st1[q][0] = st2[q][0] = a[q];
    }
    init ();
    for (int q = 1; q <= n - k + 1; ++q) {
        printf ("%d ", RMQ_n (q, q + k - 1));
    }
    printf ("\n");
    for (int q = 1; q <= n - k + 1; ++q) {
        printf ("%d ", RMQ_x (q, q + k - 1));
    }
    printf ("\n");
    return 0;
}