#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
const int MAXN =1e6+10;
typedef pair<int,int> P;
int ans[2][MAXN];
struct tree
{
    int l,r;
    int maxn;
    int minn;
};
tree arr[MAXN*4+1];
int a[MAXN];
P buildtree(int l,int r,int k)
{
    arr[k].l=l;
    arr[k].r=r;
    if(l==r)
    {
        arr[k].maxn=a[l];
        arr[k].minn=a[l];
        return P(arr[k].maxn,arr[k].minn);
    }
    int m=(l+r)>>1;
    P p1=buildtree(l,m,k<<1);
    P p2=buildtree(m+1,r,(k<<1)+1);
    int mm=max(p1.first,p2.first);
    int mii=min(p1.second,p2.second);
    arr[k].maxn=mm;
    arr[k].minn=mii;
    return P(mm,mii);
}
P query(int L,int R,int l,int r,int k)
{
    if(L<=l&&r<=R)
        return P(arr[k].maxn,arr[k].minn);
    int m=(l+r)>>1;
    P p1=P(INT_MIN,INT_MAX),p2=P(INT_MIN,INT_MAX);
    if(L<=m)
    {
        p1=query(L,R,l,m,k<<1);
    }
    if(R>m)
    {
        p2=query(L,R,m+1,r,(k<<1)+1);
    }
    return P(max(p1.first,p2.first),min(p1.second,p2.second));
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int k;
        scanf("%d",&k);
        k--;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a[i]);
        }
        buildtree(0,n-1,1);
        int p=0;
        for(int i=0;k<n;++i,++k)
        {
            P temp=query(i,k,0,n-1,1);
            ans[0][p]=temp.second;
            ans[1][p]=temp.first;
            p++;
        }
        for(int i=0;i<2;++i)
        {
            for(int j=0;j<p;++j)
            {
                if(j!=p-1) printf("%d ",ans[i][j]);
                else printf("%d\n",ans[i][j]);
            }
        }
    }
    return 0;
}

• Re:线段树G++TLE C++AC (1931) Veyron 2019-07-23 16:37:54