hdu 1754(I HATE IT)

spoiler posted @ 2011年4月11日 22:55 in ACM经典题目之线段树 , 1274 阅读

题目分析:学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

有一次参加农大月赛,因为对线段树的求区间最值的更新还是不熟练,所以出错了!缅怀!

#include<stdio.h>
int Max(int a,int b)
{
    return a>b?a:b;
}
struct node{
	int max,a,b;
}s[800000];

int t[200010];

void Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	if(x==y){
		s[num].max=t[x];
		return ;
	}
	else{
		Build(x,(x+y)/2,num+num);
		Build(((x+y)/2)+1,y,num+num+1);
		s[num].max=Max(s[num+num].max,s[num+num+1].max);
	}
}
int Query_max(int x,int y,int idx)
{
    if(x<=s[idx].a && s[idx].b<=y)
    {
        return s[idx].max;
    }
    if(y<=s[idx*2].b) return Query_max(x,y,idx*2);
    else if(x>=s[idx*2+1].a) return Query_max(x,y,idx*2+1);
    else return Max(Query_max(x,s[idx*2].b,idx*2),Query_max(s[idx*2+1].a,y,idx*2+1));
}
int modify(int x,int y,int num){
	if(s[num].a==x&&s[num].b==x){
		s[num].max=y;	
		return 0;
	}
	else{
		if(x<=s[num+num].b)
			modify(x,y,num+num);
		else 
			modify(x,y,num+num+1);
		s[num].max=Max(s[num+num].max,s[num+num+1].max);
	}
}

int main(){
	int n,cas,i,x,y;
	char c;
	while(scanf("%d %d",&n,&cas)!=EOF){
		for(i=1;i<=n;i++)
			scanf("%d",&t[i]);
		Build(1,n,1);
		while(cas--){
			getchar();
			scanf("%c %d %d",&c,&x,&y);
			if(c=='Q'){
				printf("%d\n",Query_max(x,y,1));		
			}
			else {
				modify(x,y,1);
			}
		}
		
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter