滑动窗口

题意:就是一个区间k向右移动,然后先输出区间每次移动后的区间里面最小的,结束后,换行,再下来再输出最大的
题解:板子st表

   #include<cstdio>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int n,k;
    int dmax[1000001],dmin[1000001];
    int init() //预处理
    {
        int j=1;
        for(j=1;j*2<=k;j*=2)
        {
            for(int i=0;i+j<n;i++)
            {
                dmin[i]=min(dmin[i+j],dmin[i]);
                dmax[i]=max(dmax[i+j],dmax[i]);
            }
        }
        return j;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            cin>>dmin[i];
            dmax[i]=dmin[i];
        }
        int j=init(); //保存求得的最大j
        for(int i=0;i+k<=n;i++)
        {
            cout<<min(dmin[i],dmin[i+k-j])<<' ';
        }
        cout<<endl;
        for(int i=0;i+k<=n;i++)
        {
            cout<<max(dmax[i],dmax[i+k-j])<<' ';
        }
        cout<<endl;
        return 0;
}

本题多解:线段树,树状数组,单调栈都行(线段树90%........)