線段樹解決HDOJ 1754
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。
在每個測試的第一行，有兩個正整數 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
一次AC，感覺不錯喲!嘿嘿！
另外，在POJ上也有這道題目，但是，
在POJ上的時間好像是1000ms,我的
是2031ms,所以我的代碼在那里會超
時的。有很多優化的方法，自己上網
搜索去吧。
View Code
#include "iostream" using namespace std; struct Node { int left, right, mid, score; }; Node Tree[600000]; void BuildTree(int level, int left, int right){ //建樹 Tree[level].score = -1; Tree[level].left = left; Tree[level].right = right; Tree[level].mid = (left+right)/2; if(left==right){ return; } else{ BuildTree(2*level, left, Tree[level].mid); BuildTree(2*level+1, Tree[level].mid+1, right); } } void Insert(int level, int stuID, int score){ if(stuID==Tree[level].left && stuID==Tree[level].right){ //遞歸的結束條件 Tree[level].score = score; return; } if(stuID>Tree[level].mid){ //往右邊搜索 if(score>Tree[level].score) //搜索過程中更新最大值 Tree[level].score = score; Insert(2*level+1, stuID, score); } else if(stuID<=Tree[level].mid){ //往左邊搜索 if(score>Tree[level].score) //搜索過程中更新最大值 Tree[level].score = score; Insert(2*level, stuID, score); } } int Find(int level, int left, int right){ if(left==Tree[level].left && right==Tree[level].right){ return Tree[level].score; } else if(left > Tree[level].mid){ //向右邊搜索 Find(2*level+1, left, right); } else if(right <= Tree[level].mid){ //向左邊搜索 Find(2*level, left, right); } else{ //向兩邊搜索，取較這邊中最大數的較大者 int a=Find(2*level, left, Tree[level].mid); int b=Find(2*level+1, Tree[level].mid+1, right); return a>b?a:b; } } int main() { int numofstu, numofoper; while(cin>>numofstu>>numofoper){ BuildTree(1, 1, 200000); int score, stuID, left, right; char op; for(int i=1; i<=numofstu; i++){ cin>>score; Insert(1, i, score); } while(numofoper--){ cin>>op; if(op=='Q'){ cin>>left>>right; cout<<Find(1, left, right)<<endl; } else{ cin>>stuID>>score; Insert(1, stuID, score); } } } }
posted on 2011-10-01 17:05 More study needed. 閱讀(279) 評論(0) 收藏 舉報
浙公網安備 33010602011771號