首页 > 代码库 > HDU I Hate It
HDU I Hate It
题目意思很简单,很裸的线段树。
有是一道单点更新问题,是单点更新+区间最大值。
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; #define L(x) (x<<1) #define R(x) (x<<1|1) #define lson lft,mid,rt << 1 #define rson mid+1,rht,rt << 1 | 1 #define MID(a,b) (a+((b-a)>>1)) #define INF 1<<30 const int MAXN = 200005; struct Node{ int lft,rht,mx; int mid(){return MID(lft,rht);} }; Node tree[4*MAXN]; int y[MAXN],n,m; class Segtree{ public: void Build(int lft,int rht,int rt){ tree[rt].lft = lft; tree[rt].rht = rht; tree[rt].mx = -INF; if(lft == rht) tree[rt].mx = y[lft]; else{ int mid = tree[rt].mid(); Build(lson); Build(rson); tree[rt].mx = max(tree[L(rt)].mx,tree[R(rt)].mx); } } void Update(int pos,int rt,int val){ int lft = tree[rt].lft,rht = tree[rt].rht; if(lft == rht){ tree[rt].mx = val; } else{ int mid = tree[rt].mid(); if(pos <= mid) Update(pos,L(rt),val); else Update(pos,R(rt),val); tree[rt].mx = max(tree[L(rt)].mx,tree[R(rt)].mx); } } int Query(int st,int ed,int rt){ int lft = tree[rt].lft,rht = tree[rt].rht; if(st <= lft&&rht <= ed) return tree[rt].mx; else{ int mid = tree[rt].mid(); int mx1 = -INF,mx2 = -INF; if(st <= mid) mx1 = Query(st,ed,L(rt)); if(ed > mid) mx2 = Query(st,ed,R(rt)); return max(mx1,mx2); } } }; int main() { while(~scanf("%d%d",&n,&m)) { Segtree seg; char op[5]; int a,b; for(int i = 1;i <= n;++i) scanf("%d",&y[i]); seg.Build(1,n,1); while(m--){ scanf("%s%d%d",op,&a,&b); if(op[0] == 'Q') printf("%d\n",seg.Query(a,b,1)); else seg.Update(a,1,b); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。