HDOJ 1754 I hate it(線段樹+區間最大值)

火盤古校園招聘開始！

I Hate It Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 83211    Accepted Submission(s): 31986 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專場   Recommend lcy   |   We have carefully selected several similar problems for you:   1166  1698  1542  1394  2795

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>

const int MAX_N = 200000;
int pos;

int dat[MAX_N<<2];

using namespace std;


void update(int k)//更新
{
	while (k>0)
	{
		k = (k - 1) / 2;
		dat[k] = max(dat[2 * k + 1] , dat[2 * k + 2]);
	}
}



//求[a,b)之間的和
//k 是節點編号， l和r表示對應[l,r)區間
int querya(int a, int b,int k,int l,int r)
{
	
	//[a,b)和[l,r)不相交
	if (r <= a || b <= l)return 0;
	//[a,b)完全包含[l,r)
	if (a <= l&&r <= b)return dat[k];
	else 
	{
		//左邊的和+右邊的和
	int vl= querya(a, b, k * 2 + 1, l, (l + r) / 2);
	int vr= querya(a, b, k * 2 + 2, (l + r) / 2,r );
		return max(vl,vr);
	}

}

int main()
{
	int n, m;
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		pos = 1;
		while (pos<n)
		{
			pos *= 2;
		}
		memset(dat, 0, sizeof(dat));
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &dat[pos - 1 + i]);//葉子的第一個結點是pos-1
			update(pos - 1 + i);
		}
		char s[10];
		int a, b;
		for (int i = 0; i < m; i++)
		{
			scanf("%s", s);
			scanf("%d%d", &a, &b);
			a--;//從1開始
			if (s[0] == 'U')
			{
				dat[pos - 1 + a] = b;
				update(pos - 1 + a);
			}
			else if (s[0] == 'Q')
			{
				printf("%d\n", querya(a, b, 0, 0, pos));
			}
		}
	}
	return 0;
}