线段树 + 快读 卡第十个点967ms AC

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define lid (id << 1)
#define rid (id << 1) | 1

int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return out * flag;
    }

const int maxn = 1000100;
int num,k;
int a[maxn];
struct sag_tree{
    int l,r;
    int max,min;
    }tree[maxn << 2];

void build(int id,int l,int r){
    tree[id].l = l;
    tree[id].r = r;
    if(l == r){
        tree[id].max = a[l];
        tree[id].min = a[l];
        return;
        }
    int mid = (l + r) >> 1;
    build(lid,l,mid);
    build(rid,mid + 1,r);
    tree[id].max = max(tree[lid].max,tree[rid].max);
    tree[id].min = min(tree[lid].min,tree[rid].min);
    }
int querymax(int id,int l,int r){
    if(tree[id].l == l && tree[id].r == r){
        return tree[id].max;
        }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if(mid < l){
        return querymax(rid,l,r);
        }
    else if(mid >= r){
        return querymax(lid,l,r);
        }
    else{
        return max(querymax(lid,l,mid),querymax(rid,mid + 1,r));
        }
    }
int querymin(int id,int l,int r){
    if(tree[id].l == l && tree[id].r == r){
        return tree[id].min;
        }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if(mid < l){
        return querymin(rid,l,r);
        }
    else if(mid >= r){
        return querymin(lid,l,r);
        }
    else{
        return min(querymin(lid,l,mid),querymin(rid,mid + 1,r));
        }
    }
int main(){
    num = RD();k = RD();
    for(int i = 1;i <= num;i++){a[i] = RD();}
    build(1,1,num);
    for(int i = 1;i <= num - k + 1;i++){
        printf("%d ",querymin(1,i,i + k - 1));
        //cout<<querymin(1,i,i + k - 1)<<" ";
        }
    printf("\n");
    for(int i = 1;i <= num - k + 1;i++){
        printf("%d ",querymax(1,i,i + k - 1));
        //cout<<querymax(1,i,i + k - 1)<<" ";
        }
    return 0;
    }