【题解】Luogu P2251 【质量检测】

这题可以线段树啦

线段树的讲解可看讲解

这里只需要维护一个区间最小值就好了，而且都不用去写修改的方法，只用建树和查询就好了。

#include<cstdio>

const int MAXN = 1000000 + 6;
int a[MAXN];

class SegmentTree{//线段树结构体 
    public:int l,r;
    public:int data;
};
SegmentTree t[MAXN * 4];//用来存线段树 

inline int LEFT(int x){return x << 1;}//求左儿子 
inline int RIGHT(int x){return x << 1 | 1;}//求右儿子 
inline int MID(int l,int r){return (l + r) >> 1;}//求中值 
inline int min(int a,int b){return a < b ? a : b;}//求最小值 

void build(int p,int l,int r){//递归建树 
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].data = a[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));//建左儿子 
    build(RIGHT(p),MID(l,r) + 1,r);//建右儿子 
    t[p].data = min(t[LEFT(p)].data,t[RIGHT(p)].data);//维护最小值 
}

void change(){}//修改，更新操作，都不用写233 

int ask(int p,int l,int r){//查询 
    if(l <= t[p].l && r >= t[p].r){//如果查询区间完全覆盖当且结点区间，则直接返回 
        return t[p].data;
    }
    int ans = 0x7fffffff;//最小值赋正无穷，而最大值就赋负无穷 
    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,m;
    scanf("%d %d",&n,&m);

    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);//建树 

    for(int i = 1;i <= n - m + 1;i++)
        printf("%d\n",ask(1,i,i + m - 1));//查询 

    return 0;
}