首页 > 代码库 > HDU 1754 I Hate It
HDU 1754 I Hate It
题解:线段树单点更新区间求极值。
#include <cstdio>#include <algorithm>using namespace std;int a,b,q[200005],t[1200000];void build(int l,int r,int x){ int mid=(l+r)>>1; if(l==r){t[x]=q[mid];return;} build(l,mid,x<<1); build(mid+1,r,x<<1|1); t[x]=max(t[x<<1],t[x<<1|1]);}int query(int l,int r,int x){ if(a<=l&&b>=r)return t[x]; else{ int mid=(l+r)>>1; if(b<=mid)return query(l,mid,x<<1); else if(a>mid)return query(mid+1,r,x<<1|1); else return max(query(l,mid,x<<1),query(mid+1,r,x<<1|1)); }}void modify(int l,int r,int x){ if(l==r){t[x]=b;return;} int mid=(l+r)>>1; if(a<=mid)modify(l,mid,x<<1),t[x]=max(t[x<<1],t[x<<1|1]); else{modify(mid+1,r,x<<1|1),t[x]=max(t[x<<1],t[x<<1|1]);}}int main(){ int m,n; char op[3]; while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++)scanf("%d",&q[i]); build(1,n,1); while(m--){ scanf("%s%d%d",&op,&a,&b); if(op[0]==‘Q‘)printf("%d\n",query(1,n,1)); else modify(1,n,1); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。