HDu 1754 I hate it(セグメントツリー)


#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct student
{
	int left, mid, right;
	int max;
}stu[800000];
int score[200001];
int max1, max2;
void Create(int s, int e, int n)
{
	stu[n].left=s;
	stu[n].right=e;
	stu[n].mid=(s+e)/2;
	stu[n].max=0;
	if( e-s==1) return;
	Create(s, stu[n].mid, 2*n);
	Create(stu[n].mid, e, 2*n+1);
}
//    
void Insert(int score, int i, int n)
{
	if( score>stu[n].max)
		stu[n].max=score;
	if(stu[n].right-stu[n].left==1) return;
	if(i<stu[n].mid) Insert(score, i, 2*n);//      
	else if(i>=stu[n].mid) Insert(score, i, 2*n+1);
}
int Query(int s, int e, int n)
{
	if(stu[n].left==s && stu[n].right==e)
		return stu[n].max;
	if( e<=stu[n].mid) return Query(s, e, 2*n);
	else if( s>=stu[n].mid) return Query(s, e, 2*n+1);
	else
	{
		max1=Query(s, stu[n].mid, 2*n);
		max2= Query(stu[n].mid, e, 2*n+1);
		return max1>max2?max1:max2;
	}
}
int main()
{
	int n, m, a, b, i;
	char c;
	while( scanf("%d %d", &n, &m)!= EOF)
	{
		Create(1,n+1, 1);
		for(i=1; i<=n; i++)
		{
			scanf("%d", score+i);
			Insert(score[i], i, 1);
		}
		while( m-- )
		{
			getchar();
			scanf("%c %d %d", &c, &a, &b);
			if( c=='Q')
				printf("%d
", Query(a, b+1, 1));// , b+1 else Insert(b, a, 1); } } }