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): 37627 Accepted Submission(s): 14893
Problem Description
很多學校流行一種比較的習慣。老師們很喜歡詢問，從某某到某某當中，分數最高的是多少。
這讓很多學生很反感。
不管你喜不喜歡，現在需要你做的是，就是按照老師的要求，寫一個程序，模擬老師的詢問。當然，老師有時候需要更新某位同學的成績。
Input
本題目包含多組測試，請處理到文件結束。
在每個測試的第一行，有兩個正整數 N 和 M ( 0
學生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
HintHuge input,the C function scanf() will work better than cin
線段樹（區間最值）：
#include
#include
#include
#include
using namespace std;
int max(int a,int b)
{
return (a>b?a:b);
}
int a[200000];
struct Node
{
int left,right;
int t;
}node[4*200000];
void MakeTree(int l,int r,int i)
{
node[i].left=l;
node[i].right=r;
if(l==r)
{
node[i].t=a[l];
return ;
}
int mid=(l+r)/2;
MakeTree(l,mid,2*i);
MakeTree(mid+1,r,2*i+1);
node[i].t=max(node[2*i].t,node[2*i+1].t);
}
void UpdateTree(int i,int x,int y)
{
int l=node[i].left;
int r=node[i].right;
int mid=(l+r)/2;
if(x==l&&x==r)
{
node[i].t=y;
return ;
}
if(x>mid)
UpdateTree(2*i+1,x,y);
else
UpdateTree(2*i,x,y);
node[i].t=max(node[2*i].t,node[2*i+1].t);
}
int QueryTree(int x,int y,int i)
{
if(node[i].left==x && node[i].right==y)
return node[i].t;
//if(node[i].left==node[i].right)
//return 0;
int m=(node[i].left+node[i].right)/2;
if(x>m)
return QueryTree(x,y,2*i+1);
else if(y<=m)
return QueryTree(x,y,2*i);
else
return max(QueryTree(x,m,2*i),QueryTree(m+1,y,2*i+1));
}
int main ()
{
int T,n,m;
int i,j,x,y;
char c[10];
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
MakeTree(1,n,1);
getchar();
for(j=1;j<=m;j++)
{
scanf("%c%d%d",&c[0],&x,&y);
getchar();
if(c[0]=='U')
UpdateTree(1,x,y);
else
cout<
