hdu 1754 I Hate It 【线段树】

2019-11-08 02:15:50

字体：大中小

来源：转载

供稿：网友

题目链接：http://acm.hdu.edu.cn/showPRoblem.php?pid=1754 题意：中文题解析：线段树，单点修改，区间查询

#include <bits/stdc++.h>using namespace std;const int maxn = 200000+500;struct node{ int l,r; int maxx;}tree[4*maxn];int a[maxn];void push_up(int i){ tree[i].maxx = max(tree[i<<1].maxx,tree[i<<1|1].maxx);}void build(int i,int l,int r){ tree[i].l = l,tree[i].r = r; tree[i].maxx = 0; if(l==r) { tree[i].maxx = a[r]; return ; } int mid = (l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); push_up(i);}void update(int i,int pos,int val){ int l = tree[i].l; int r = tree[i].r; if(l==r && l==pos) { tree[i].maxx = val; return ; } int mid = (l+r)>>1; if(mid>=pos) update(i<<1,pos,val); else update(i<<1|1,pos,val); push_up(i);}int query(int i,int l,int r){ int L = tree[i].l; int R = tree[i].r; if(l<=L && R<=r) return tree[i].maxx; int mid = (L+R)>>1; int ans = 0; if(mid<r) ans = query(i<<1|1,l,r); if(mid>=l) ans = max(ans,query(i<<1,l,r)); return ans;}int main(void){ int n,m; while(~scanf("%d %d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); while(m--) { char op[10]; int x,y; scanf("%s %d %d",op,&x,&y); if(op[0]=='U') update(1,x,y); else printf("%d/n",query(1,x,y)); } } return 0;}

上一篇：线段树模板

下一篇：LINUX下 PCB的结构task_struct构造分析