【题解】Luogu P1440 【求m区间内的最小值】

这里又被卡常，朴素线段树就是慢了，所以打了zkw线段树，然后$RE$两个点，好像是开区间问题，索性放弃zkw线段树，开始毒瘤优化，加个读入输出优化和开$-o2$还是跑过去了。

朴素版：

#include<cstdio>

const int MAXN = 2000000 + 6;
const int INT_MAX = 0x7fffffff;

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline int max(int a,int b){return a > b ? a : b;}

int read(){
    int op = 1,ans = 0;char s = getchar();
    while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}
    while(s >='0' && s <='9'){ans = ans * 10 + s - '0';s = getchar();}
    ans *= op;
    return ans;
}
void print(int x){
    if(x < 0){putchar('-');x = -x;}
    if(x > 9){print(x / 10);}
    putchar(x % 10 + '0');
}
void println(int x){
    print(x);
    putchar('\n');
}

class SegmentTree{
    public:int l,r;
    public:int min;
};
SegmentTree t[MAXN * 4];

inline int MID(int l,int r){return (l + r) >> 1;}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].min = read();
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    t[p].min = min(t[LEFT(p)].min,t[RIGHT(p)].min);
}

int ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].min;
    }
    int ans = INT_MAX;
    if(l <= MID(t[p].l,t[p].r)){
        ans = min(ans,ask(LEFT(p),l,r));
    }
    if(r > MID(t[p].l,t[p].r)){
        ans = min(ans,ask(RIGHT(p),l,r));
    }
    return ans;
}

int main(){
    int n = read(),m = read();
    
    build(1,1,n);
    
    println(0);
    
    for(int i = 1;i < n;i++){
        if(i - m <= 0){
            println(ask(1,1,i));
        }else{
            println(ask(1,i - m + 1,i));
        }
    }
    
    return 0;
}

zkw线段树，它常数太小了，都不用开快读：

#include<cstdio>

const int MAXN = 2000000 + 6;
const int INT_MAX = 0x7fffffff;

class zkwSegmentTree{
    public:int min;
};
typedef zkwSegmentTree zkw;
zkw t[MAXN * 2];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline int max(int a,int b){return a > b ? a : b;}

int n,M,m;

void build(){
    for(M = 1;M < (n + 2);M <<= 1);
    for(int i = M + 1;i <= M + n;i++){
        int gg;
        scanf("%d",&gg);
        t[i].min = gg;
    }
    for(int i = M - 1;i;i--){
        t[i].min = min(t[LEFT(i)].min,t[RIGHT(i)].min);
    }
}

int ask(int l,int r){
    int ans = INT_MAX;
    for(l += M - 1,r += M + 1;l ^ r ^ 1;l >>= 1,r >>= 1){
        if(~l & 1){
            ans = min(ans,t[l ^ 1].min);
        }
        if(r & 1){
            ans = min(ans,t[r ^ 1].min);
        }
    }
    return ans;
} 

int main(){
    scanf("%d %d",&n,&m);
    
    build();
    
    printf("0\n");
    
    for(int i = 1;i < n;i++){
        if(i - m <= 0){
            printf("%d\n",ask(1,i));
        }else{
            printf("%d\n",ask(i - m + 1,i));    
        }
    }
    
    return 0;
}