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 我感觉这样不行吧