救救孩子

P1886 滑动窗口 /【模板】单调队列

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

萌新初学线段树,炸了 不输出,求助dalao

#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 我不认识你 @ 2019-10-02 18:33:22

@Lates


by Lates @ 2019-10-02 18:34:03

@我不认识你 位运算不用加()


by Lates @ 2019-10-02 18:34:24

@True_konjac st表mle,不想写


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

@WEMS_pzc 但是WA了现在


by pzc2004 @ 2019-10-02 18:35:31

@Lates 你的快读为什么要用(ch^'0')啊


by pzc2004 @ 2019-10-02 18:35:37

@我不认识你 不用


by pzc2004 @ 2019-10-02 18:35:51

@我不认识你 位运算优先级低于加减


by 我不认识你 @ 2019-10-02 18:35:55

我吃鲸了


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

@WEMS_pzc 听说位运算快一点QAQ


by pzc2004 @ 2019-10-02 18:40:34

@Lates 我感觉这样不行吧


上一页 | 下一页