学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1754

做了hdu 1166以后，感觉这个题好简单，只不过那个是区间求和，这个是区间求最值而已。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 200005;

struct line
{
	int l;
	int r;
	int max_score;
}tree[4*maxn];

int n,m;
int score[maxn];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	if(l == r)
	{
		tree[v].max_score = score[r];
		return;
	}

	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
	tree[v].max_score = max(tree[v*2].max_score,tree[v*2+1].max_score);
}

int query(int v, int l, int r)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		return tree[v].max_score;
	}

	int mid = (tree[v].l + tree[v].r)>>1;
	if(r <= mid)
		return query(v*2,l,r);
	else if(l > mid)
		return query(v*2+1,l,r);
	else return max(query(v*2,l,mid),query(v*2+1,mid+1,r));
}

void update(int v, int posi, int vali)
{
	if(tree[v].l == tree[v].r)
	{
		tree[v].max_score = vali;
		return;
	}
	int mid = (tree[v].l+tree[v].r)>>1;
	if(posi <= mid)
		update(v*2,posi,vali);
	else
		update(v*2+1,posi,vali);
	tree[v].max_score = max(tree[v*2].max_score,tree[v*2+1].max_score);
}

int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		for(int i = 1; i <= n; i++)
			scanf("%d",&score[i]);

		build(1,1,n);

		char ch[2];
		int l,r,ans;
		int pos,val;
		for(int i = 1; i <= m; i++)
		{
			scanf("%s",ch);
			if(ch[0] == 'Q')
			{
				scanf("%d %d",&l,&r);
				ans = query(1,l,r);
				printf("%d\n",ans);
			}
			else
			{
				scanf("%d %d",&pos,&val);
				update(1,pos,val);
			}
		}
	}
	return 0;
}