题解 P1886 【滑动窗口】

· · 题解

看到很多(普通的)线段树t了几个点的，很心疼...明明标签里有线段树，却过不了。

而我就偏不信这个邪，普通的线段树敲完后，各种优化无数次，t了最后一个点无数次...最后在政治考场想到一种清奇的操作：

查询函数一次性返回最大和最小值

用结构体来实现就好啦！查询最小值的时候顺便把最大值存起来，到时候直接输出即可。

代码如下

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000002;
int a[maxn],i,n,k;
struct sao{
    int mi,ma;
}que;//结构体，存最大最小值
inline void read(int &x){//快读
    char c;int flag=0;
    while(!isdigit(c=getchar()))
        if(c=='-') flag=1;
    x=c-'0';
    while(isdigit(c=getchar()))
        x=x*10+c-'0';
    if(flag) x=-x;
}
struct segtree{//线段树结构
    const int inf=1<<30;
    int minv[maxn<<2],maxv[maxn<<2];
    inline void pushup(int o){
        maxv[o]=max(maxv[o<<1|1],maxv[o<<1]);
        minv[o]=min(minv[o<<1|1],minv[o<<1]);
    }
    inline void build(int o,int l,int r){
        if(l==r){minv[o]=maxv[o]=a[l];return;}
        int mid=(l+r)>>1;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        pushup(o);
    }//树也一起建
    inline sao querymin(int o,int l,int r,int ql,int qr){//操作开始
        if(ql<=l&&qr>=r)return (sao){minv[o],maxv[o]};//这里就是返回sao类型的值，实际上是两个值
        int minn=inf,maxx=-inf;
        int mid=(l+r)>>1;
        sao t;
        if(ql<=mid){t=querymin(o<<1,l,mid,ql,qr);minn=min(minn,t.mi);maxx=max(maxx,t.ma);}//用t存起来，避免重复递归
        if(qr>mid){t=querymin(o<<1|1,mid+1,r,ql,qr);minn=min(minn,t.mi);maxx=max(maxx,t.ma);}
        return (sao){minn,maxx};
    }
}seg;
int main(){
    ios::sync_with_stdio(false);//减少cin时间...虽然没用到
    read(n);read(k);
    for(i=1;i<=n;i++)read(a[i]);
    seg.build(1,1,n);
    for(i=1;i<=n-k+1;i++){
        que=seg.querymin(1,1,n,i,i+k-1);
        printf("%d ",que.mi);//直接输出最小值
        a[i]=que.ma;//存最大值
    }
    puts("");
    for(i=1;i<=n-k+1;i++)printf("%d ",a[i]);//输出最大值
    return 0;
}