首页 > 代码库 > NBUT 1680 卖瓜（线段树）
NBUT 1680 卖瓜（线段树）
题目链接：https://ac.2333.moe/Problem/view.xhtml?id=1680
题意：中文题
现在看觉得就是道水题，罒ω罒。
但是几天前比赛的时候没写出来，写下题解纪念一波，≡￣﹏￣≡。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 int ans1,ans2; 6 const int INF=0x3f3f3f3f; 7 const int N=11111; 8 struct Tree{ 9 int l,r;10 int MAX,MIN;11 };12 Tree tree[4*N];13 14 void pushup(int x){15 int tmp=x<<1;16 tree[x].MAX=max(tree[tmp].MAX,tree[tmp+1].MAX);17 tree[x].MIN=min(tree[tmp].MIN,tree[tmp+1].MIN); 18 }19 20 void build(int l,int r,int x){21 tree[x].l=l;22 tree[x].r=r;23 if(l==r){24 scanf("%d",&tree[x].MAX);25 tree[x].MIN=tree[x].MAX;26 return ;27 } 28 int tmp=x<<1;29 int mid=(l+r)>>1;30 build(l,mid,tmp);31 build(mid+1,r,tmp+1);32 pushup(x);33 }34 35 void update(int l,int r,int value,int x){36 if(tree[x].l>r||tree[x].r<l) return ;37 if(l==tree[x].l&&r==tree[x].r){38 tree[x].MAX=value;39 tree[x].MIN=value;40 return ;41 }42 int tmp=x<<1;43 update(l,r,value,tmp);44 update(l,r,value,tmp+1);45 pushup(x);46 }47 48 void query(int l,int r,int x){49 if(r<tree[x].l||l>tree[x].r) return ;50 if(l<=tree[x].l&&r>=tree[x].r){51 ans1=max(ans1,tree[x].MAX);52 ans2=min(ans2,tree[x].MIN);53 return ;54 }55 int tmp=x<<1;56 int mid=(tree[x].l+tree[x].r)>>1;57 if(r<=mid) query(l,r,tmp);58 else if(l>mid) query(l,r,tmp+1);59 else{60 query(l,mid,tmp);61 query(mid+1,r,tmp+1);62 }63 }64 65 int main(){66 int t,n,q;67 scanf("%d",&t);68 for(int k=1;k<=t;k++){69 scanf("%d %d",&n,&q);70 build(1,n,1);71 int op,l,r;72 for(int i=1;i<=q;i++){73 scanf("%d %d %d",&op,&l,&r);74 if(op==1){ 75 ans1=-1;76 ans2=INF;77 query(l,r,1);78 printf("%d\n",ans1-ans2);79 }80 else if(op==2){81 update(l,l,r,1);82 }83 }84 }85 return 0;86 }
NBUT 1680 卖瓜（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。