救救孩子

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 pzc2004 @ 2019-10-02 18:16:26

为什么本地运行CE了

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

@WEMS_pzc 艾玛，发错代码了

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

@WEMS_pzc

#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=0,q=0;
    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=0,q=0;
    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 Lates @ 2019-10-02 18:20:56

@WEMS_pzc 麻烦dalao帮我这个蒟蒻看一下

by pzc2004 @ 2019-10-02 18:24:09

@Lates 你的Query_Max L R 和l r弄反了

by s_ShotღMaki @ 2019-10-02 18:26:47

无空格，不代码

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

@WEMS_pzc 哦哦哦谢谢dalao

by Lates @ 2019-10-02 18:32:18

@s_ShotღMaki %%%

by 爱晚亭哦 @ 2019-10-02 18:32:35

试试ST表

by 我不认识你 @ 2019-10-02 18:33:08

l+r>>1加个括号