Lates @ 2019-10-02 18:12:05

#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
    register int x=0,v=1,ch=getchar();
    while(!isdigit(ch)){if(ch=='-')v=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*v;
}
const int MAX=1000001;
int n,m,a[MAX];
struct Node{int maxn,minn;}tree[MAX<<2];
inline int left(int x){return x<<1;}
inline int right(int x){return x<<1|1;}
inline void pushup(int x){
    tree[x].maxn=max(tree[left(x)].maxn,tree[right(x)].maxn);
    tree[x].minn=min(tree[left(x)].minn,tree[right(x)].minn);
} 
void Build(int l,int r,int x){
    if(l==r){tree[x].maxn=tree[x].minn=a[l];return ;}
    register int mid=l+r>>1;
    Build(l,mid,left(x));Build(mid+1,r,right(x));
    pushup(x);
}
int Query_Max(int L,int R,int l,int r,int x){
    if(L<=l&&r<=R)return tree[x].maxn;
    register int mid=l+r>>1,r=0,b=0;
    if(l<=mid)r=Query_Max(L,R,l,mid,left(x));
    if(r>mid)b=Query_Max(L,R,mid+1,r,right(x));
    return max(r,b);        
}
int Query_Min(int L,int R,int l,int r,int x){
    if(L<=l&&r<=R)return tree[x].minn;
    register int mid=l+r>>1,r=0,b=0;
    if(l<=mid)r=Query_Min(L,R,l,mid,left(x));
    if(r>mid)b=Query_Min(L,R,mid+1,r,right(x));
    return min(r,b);            
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,n,1);
    for(register int i=1;i<=n-m+1;++i){
        printf("%d ",Query_Min(i,i+m-1,1,n,1));
    } 
    putchar('\n');
    for(register int i=1;i<=n-m+1;++i){
        printf("%d ",Query_Max(i,i+m-1,1,n,1));
    }
    putchar('\n');
    return 0;
}

by Lates @ 2019-10-02 18:41:31

@WEMS_pzc 应该不是快读的锅，因为我从开始用快读都是这么写的

by 爱晚亭哦 @ 2019-10-02 18:41:49

@Lates 一个二维数组做两次

by Lates @ 2019-10-02 18:44:40

@True_konjac 我试试看

by pzc2004 @ 2019-10-02 18:46:11

#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
    register int x=0,v=1,ch=getchar();
    while(!isdigit(ch)){if(ch=='-')v=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*v;
}
const int MAX=1000001;
int n,m,a[MAX];
struct Node{int maxn,minn;}tree[MAX<<2];
inline int left(int x){return x<<1;}
inline int right(int x){return x<<1|1;}
inline void pushup(int x){
    tree[x].maxn=max(tree[left(x)].maxn,tree[right(x)].maxn);
    tree[x].minn=min(tree[left(x)].minn,tree[right(x)].minn);
} 
void Build(int l,int r,int x){
    if(l==r){tree[x].maxn=tree[x].minn=a[l];return ;}
    register int mid=l+r>>1;
    Build(l,mid,left(x));Build(mid+1,r,right(x));
    pushup(x);
}
int Query_Max(int L,int R,int l,int r,int x){
    if(L<=l&&r<=R)return tree[x].maxn;
    register int mid=l+r>>1,p=-2147483648,q=-2147483648;
    if(L<=mid)p=Query_Max(L,R,l,mid,left(x));
    if(R>mid)q=Query_Max(L,R,mid+1,r,right(x));
    return max(p,q);        
}
int Query_Min(int L,int R,int l,int r,int x){
    if(L<=l&&r<=R)return tree[x].minn;
    register int mid=l+r>>1,p=2147483647,q=2147483647;
    if(L<=mid)p=Query_Min(L,R,l,mid,left(x));
    if(R>mid)q=Query_Min(L,R,mid+1,r,right(x));
    return min(p,q);            
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,n,1);
    for(register int i=1;i<=n-m+1;++i){
        printf("%d ",Query_Min(i,i+m-1,1,n,1));
    } 
    putchar('\n');
    for(register int i=1;i<=n-m+1;++i){
        printf("%d ",Query_Max(i,i+m-1,1,n,1));
    }
    putchar('\n');
    return 0;
}

by pzc2004 @ 2019-10-02 18:46:26

@Lates 改成这样试试

by Lates @ 2019-10-02 18:48:19

@WEMS_pzc 对了

by Lates @ 2019-10-02 18:48:36

@True_konjac @WEMS_pzc 谢谢大佬们

by Lates @ 2019-10-02 18:48:47

此贴完结