本文主要是介绍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<<30const 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));elseseg.Update(a,1,b);}}return 0;
}
这篇关于HDU I Hate It的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
