I Hate It

Time Limit: 9000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 54832????Accepted Submission(s): 21445


Problem Description 很多學校流行一種比較的習慣。老師們很喜歡詢問，從某某到某某當中，分數最高的是多少。
這讓很多學生很反感。

不管你喜不喜歡，現(xiàn)在需要你做的是，就是按照老師的要求，寫一個程序，模擬老師的詢問。當然，老師有時候需要更新某位同學的成績。
Input 本題目包含多組測試，請?zhí)幚淼轿募Y束。
在每個測試的第一行，有兩個正整數 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 9HintHuge input,the C function scanf() will work better than cin #include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const int MAXNODE = 524288; // 1<<19
const int MAXST = 200001;
struct STU{
?int grade;
?int left,right;
}st[MAXNODE];
int father[MAXST];
void BuildTree(int i,int left,int right){ // i是結點的序號 對應了數組下標
?st[i].left = left;
?st[i].right = right;
?st[i].grade = 0; // 初始化為0
?if (left == right){
??father[left] = i; // 為了更新的時候從下往上 一直到頂
??return;
?}
?BuildTree(i<<1, left, (int)( (right+left) / 2.0));
?BuildTree((i<<1) + 1, (int)( (right+left) / 2.0) + 1, right);
}
void UpdataTree(int ri){ // 從下往上更新
?if (ri == 1){return;}
?int fi = ri / 2; // 父結點
?int a = st[fi<<1].grade; // 該父結點的兩個子結點
?int b = st[(fi<<1)+1].grade;
?st[fi].grade = (a > b)?(a):(b);
?UpdataTree(ri/2);
}
int Max;
void Query(int i,int l,int r){ // i為區(qū)間的序號，四段查詢 即四種情況
?if (st[i].left == l && st[i].right == r)
?{ // 找到了一個完全重合的區(qū)間
??Max = (Max < st[i].grade)?st[i].grade:(Max);
?return ;
?}
?i = i << 1; // left child of the tree
?if (l <= st[i].right){ // 左區(qū)間有覆蓋
??if (r <= st[i].right) // 全包含于左區(qū)間
???Query(i, l, r);
??else // 半包含于左區(qū)間
???Query(i, l, st[i].right);
?}
?i += 1; // right child of the tree
?if (r >= st[i].left){ // 右區(qū)間有覆蓋
??if (l >= st[i].left) // 全包含于右區(qū)間
???Query(i, l, r);
??else // 半包含于左區(qū)間
???Query(i, st[i].left, r);
?}
}
int main()
{
?int N,M,mark;
?{
?while(cin>>N>>M)
??BuildTree(1, 1, N);
??for (int i= 1 ; i <= N; i++)
??{
???cin>>mark;
???st[father[i]].grade = mark; // 底層的無條件更新成績
???UpdataTree(father[i]);
??}
??while(M--){
???char o[3];int a,b;
???cin>>o>>a>>b;
???if ( o[0] == 'Q')
???{
????Max = 0;
????Query(1, a, b);
????cout<<Max<<endl;
???}
???else
???{
????st[father[a]].grade = b; // 底層的無條件更新成績
????UpdataTree(father[a]);
???}
??}
?}
?return 0;
}

總結

以上是生活随笔為你收集整理的线段树杭电1754 I hate it的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。