I Hate It

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

Problem Description

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

不管你喜不喜歡，現在需要你做的是，就是按照老師的要求，寫一個程序，模擬老師的詢問。當然，老師有時候需要更新某位同學的成績。

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

9

解析：不懂樹狀數組求區(qū)間最值的，可以看樹狀數組的應用

另外一種解法：hdu1754-線段樹

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=2e5+10;int n,m,a[maxn],c[maxn];int lowbit(int x) {return x&(-x); } void update(int i,int value) {while(i<=n){c[i]=value;for(int x=1; x<lowbit(i); x<<=1){c[i]=max(c[i],c[i-x]);}i+=lowbit(i);}return ; } int query(int l,int r) {int ans=0;while(l<=r){ans=max(ans,a[r]);r--;for(; r-l>=lowbit(r); r-=lowbit(r)){ans=max(ans,c[r]);}}return ans; } int main() {while(~scanf("%d%d",&n,&m)){for(int i=1; i<=n; i++)c[i]=0;for(int i=1; i<=n; i++){scanf("%d",&a[i]);update(i,a[i]);}while(m--){char s[5];int x,y;scanf("%s %d%d",s,&x,&y);if(s[0]=='Q'){printf("%d\n",query(x,y));}else{a[x]=y;update(x,y);}}}return 0; }

?

總結

以上是生活随笔為你收集整理的hdu1754（树状数组求最值问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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