HDU 1754 I Hate It 线段树RMQ

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

题目大意：

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

思路：

线段树即可。。

PS：某一题线段树太久没写一直调不出，先来做做水题。。

I Hate It ！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=200000;
int data[MAXN];
const int INF=-0x3fffffff;
int A[MAXN],maxv[MAXN*3];
int n,qL,qR,p,v;

void build(int k,int L,int R)
{
	if(L==R)  maxv[k]=A[L];
	else
	{
		int m=(L+R)/2;
		build(k*2,L,m);
		build(k*2+1,m+1,R);
		maxv[k]=max(maxv[k*2],maxv[k*2+1]);	
	}
}
// 查询区间[a,b] 对应区间[L,R]; 
int query(int k,int L,int R,int a,int b)
{
	int m=(L+R)/2,ans=INF;
	if(a<=L && R<=b) return maxv[k];
	if(a<=m) ans=max(ans,query(k*2,L,m,a,b));
	if(m<b)  ans=max(ans,query(k*2+1,m+1,R,a,b));
	return ans;
}

void update(int k,int L,int R,int p,int x)
{
	int m=(L+R)/2;
	if(L==R)  maxv[k]=x;
	else{
		if(p<=m)
		 	update(k*2,L,m,p,x);
		else 
			update(k*2+1,m+1,R,p,x);
		maxv[k]=max(maxv[k*2],maxv[k*2+1]);	
	} 
}

int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{		
		int temp;

		for(int i=1;i<=n;i++)
			scanf("%d",&A[i]);
			
		build(1,1,n);
		
		for(int i=0;i<m;i++)
		{
			char cmd[5];
			scanf("%s",cmd);
			if(cmd[0]==‘U‘)
			{
				scanf("%d%d",&p,&v);
				update(1,1,n,p,v);
			}
			else
			{
				scanf("%d%d",&qL,&qR);
				printf("%d\n",query(1,1,n,qL,qR));
			}
		}		
	}
	return 0;
}

HDU 1754 I Hate It 线段树RMQ,布布扣,bubuko.com

HDU 1754 I Hate It 线段树RMQ

原文：http://blog.csdn.net/murmured/article/details/21255763