hdu 1754 I Hate It (선분 트 리 업데이트 지점 의 값)

I Hate It
Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 51089    Accepted Submission(s): 20037
Problem Description
많은 학교 에서 비교 하 는 습관 이 유행한다.선생님 들 은 모모 에서 모모 까지 점수 가 가장 높 은 것 이 얼마 인지 묻 는 것 을 좋아한다.
이것 은 많은 학생 들 로 하여 금 매우 반감 을 가지 게 한다.
네가 좋아 하 든 안 좋아 하 든 지금 네가 해 야 할 일 은 바로 선생님 의 요구 에 따라 프로그램 을 써 서 선생님 의 질문 을 모 의 하 는 것 이다.물론 선생님 은 어떤 학우 의 성적 을 갱신 해 야 할 때 가 있다.
 
Input
이 문 제 는 여러 그룹의 테스트 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.
각 테스트 의 첫 줄 에는 두 개의 정수 N 과 M (0 < N < = 20000, 0 < M < 5000) 이 있 는데 각각 학생 의 수량 과 조작 수량 을 대표 한다.
학생 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 로 변경 하 라 는 업데이트 작업 이 라 고 밝 혔 다.
 
Output
매번 문의 조작 에 대해 한 줄 에서 최고 성적 을 출력 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    5
6
5
9


    
    
    
    
 
     
 
      Hint 
     
Huge input,the C function scanf() will work better than cin 
    
    
    
    
     
   
   
   
   

 
Author
linle
 
Source
2007 성 경기 합숙 훈련 팀 연습 경기 (6)linle 특별 공연
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1166  1698  1542  1394  2795 
 
Statistic |  Submit |  Discuss |  Note
그렇게 많은 검색 횟수 를 보고 선분 트 리 를 사용 한 것 은 의심 할 여지 가 없다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
	int left,right,val;
}c[200000*3];
void build_tree(int l,int r,int root)//  
{
	c[root].left=l;
	c[root].right=r;
	if(l==r)
	{
		scanf("%d",&c[root].val);
		return ;
	}
	int mid=(c[root].left+c[root].right)/2;
	build_tree(l,mid,root*2);
	build_tree(mid+1,r,root*2+1);
	c[root].val=max(c[root*2].val,c[root*2+1].val);
}
void search_tree(int l,int r,int root,int &Max)//  
{
	if(c[root].left==l&&c[root].right==r)
	{
		Max=c[root].val;
		return ;
	}
	int mid=(c[root].left+c[root].right)/2;
	if(mid<l)
	search_tree(l,r,root*2+1,Max);
	else if(mid>=r)
	search_tree(l,r,root*2,Max);
	else
	{
		int Max1;
		search_tree(l,mid,root*2,Max);
		search_tree(mid+1,r,root*2+1,Max1);
		Max=max(Max,Max1);
	}
}
void update_tree(int pos,int root,int x)//   
{
	if(c[root].left==c[root].right&&c[root].left==pos)
	{
		c[root].val=x;
		return ;
	}
	int mid=(c[root].left+c[root].right)/2;
	if(mid<pos)
	update_tree(pos,root*2+1,x);
	else
	update_tree(pos,root*2,x);
	c[root].val=max(c[root*2].val,c[root*2+1].val);
}
int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(&c,0,sizeof(&c));
		build_tree(1,n,1);
		getchar();
		for(int i=0;i<m;i++)
		{
			char ch;
			scanf("%c",&ch);
			if(ch=='Q')
			{
				int a,b,Max;
				scanf("%d %d",&a,&b);
				getchar();
				if(a<b)
				search_tree(a,b,1,Max);
				else
				search_tree(b,a,1,Max);
				printf("%d
",Max);
			}
			if(ch=='U')
			{
				int a,b;
				scanf("%d %d",&a,&b);
				getchar();
				update_tree(a,1,b);
			}
		}
	}
	return 0;
}