首页 > 代码库 > hdu 1754 I Hate It(单点更新,区段查最值)
hdu 1754 I Hate It(单点更新,区段查最值)
题意:
N个成绩。M个操作。
Q a b:查询第a个到第b个成绩中最高成绩
U a b:将第a个成绩改成b
思路:
看代码,,
代码:
const int maxn = 200010;int maxs[maxn<<2];int N,M;void PushUp(int rt){ maxs[rt] = max( maxs[rt<<1], maxs[rt<<1|1] );}void build(int l,int r,int rt){ if(l==r){ scanf("%d",&maxs[rt]); return; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt);}void update(int p,int add,int l,int r,int rt){ if(l==r){ maxs[rt] = add; return; } int m = (l + r) >> 1; if(p <= m) update(p,add,lson); else update(p,add,rson); PushUp(rt);}int query(int L,int R,int l,int r,int rt){ if(L<=l && r<=R){ return maxs[rt]; } int m = (l + r) >> 1; int ret = 0; if(L <= m) ret = max( ret, query(L,R,lson) ); if(R > m) ret = max( ret, query(L,R,rson) ); return ret;}int main(){ while(scanf("%d%d",&N,&M)!=EOF){ build(1,N,1); for(int i=1;i<=M;++i){ char c; int a,b; getchar(); scanf("%c%d%d",&c,&a,&b); if(c == ‘Q‘) printf("%d\n",query(a,b,1,N,1)); else if(c == ‘U‘) update(a,b,1,N,1); } }}
hdu 1754 I Hate It(单点更新,区段查最值)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。