Hdu 1754【線分樹】

/*I Hate It 
Time Limit : 9000/3000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 0   Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia 
Font Size: ← →
Problem Description
             。        ，        ，        。
         。

       ，        ，         ，     ，       。  ，                。 
Input
         ，        。
         ，       N   M ( 0<N<=200000,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   
*/ 
#include<stdio.h>
int segtree[800001], n, m, data[200010], max;
int Max(int a, int b)
{
	return a>b?a:b;
}
void build_segtree(int l, int r, int rt)
{
	if(l == r)
	{ 
		scanf("%d", &segtree[rt] );//leaf num
		return ;
	}
	int k = (l + r)>>1; //save time
	build_segtree(l, k, rt<<1);
	build_segtree(k + 1,  r, rt<<1|1);
	segtree[rt] = Max(segtree[rt<<1], segtree[rt<<1|1]);//back
}
void update(int a, int b, int l, int r, int rt)
{
	if(l ==  r)
	{
		segtree[rt] = b;
		return ;
	}
	int k = (l+r)>>1;//save time
	if(a <= k)
	update(a, b, l, k, rt<<1);
	else 
	update(a, b, k + 1, r, rt<<1|1);
	segtree[rt] = Max(segtree[rt<<1], segtree[rt<<1|1]);//back
}
int question(int a, int b, int l , int r, int rt)
{
	if(a <= l && r <= b)//visit 
	{
		return segtree[rt];
	}
	int sum = 0, k = (l+r)>>1;
	if( a <= k)//the left part
	sum = Max(sum, question( a, b, l , k, rt<<1) );
	if(b > k )//the right part
	sum = Max(sum, question( a, b, k+1, r, rt<<1|1) );
	return sum;
}
int main()
{
	int i , j, a, b;
	char ch;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		build_segtree( 1 , n , 1 );
		for(i = 0; i < m; ++i)
		{
			getchar();
			scanf("%c%d%d", &ch, &a, &b);
			if(ch == 'U')//update
			{
				update(a, b, 1, n, 1);//update the segtree 
			}
			else
			{
				printf("%d
", question(a , b , 1, n, 1) );
			}
		}
	}
	return 0;
}

标题:標準の線分ツリーで、ポイント更新と区間クエリの最大値が主な操作です.
考え方:セグメントツリーテンプレート.
注意:ここには穴があいています.Maxはマクロで定義しないで、関数で作ってください.そうしないとタイムアウトします.の(関数呼び出しパラメータは計算済みで、一度だけ計算されます.マクロ定義は計算されず、実行時に毎回計算されます.)