I Hate It

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

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 題解：線段樹模板 代碼： 1 #include<stdio.h> 2 #include<string.h> 3 #define lson root<<1,l,mid 4 #define rson root<<1|1,mid+1,r 5 const int MAXN=200010<<2; 6 #define X int root,int l,int r 7 #define Y 1,1,N 8 #define MAX(x,y)(x>y?x:y) 9 #define NOW tree[root]=MAX(tree[root<<1],tree[root<<1|1]) 10 int tree[MAXN]; 11 int A,B,anser; 12 void build(X){ 13 if(l==r)scanf("%d",&tree[root]); 14 else { 15 int mid=(l+r)>>1; 16 build(lson); 17 build(rson); 18 NOW; 19 } 20 } 21 void update(X){ 22 if(l==A&&r==A)tree[root]=B; 23 else{ 24 int mid=(l+r)>>1; 25 if(A<=mid)update(lson); 26 else update(rson); 27 NOW; 28 } 29 } 30 void print(X){ 31 if(A<=l&&B>=r)anser=MAX(anser,tree[root]);//這個是從線段樹的頂往下搜的 32 else{ 33 int mid=(l+r)>>1; 34 if(A<=mid)print(lson);//記住mid 35 if(B>mid)print(rson); 36 NOW; 37 } 38 } 39 int main(){ 40 int N,M; 41 char s[2]; 42 while(~scanf("%d%d",&N,&M)){ 43 build(Y); 44 while(M--){ 45 scanf("%s",s); 46 if(!strcmp(s,"U")){ 47 scanf("%d%d",&A,&B); 48 update(Y); 49 } 50 else{ 51 anser=0; 52 scanf("%d%d",&A,&B); 53 print(Y); 54 printf("%d\n",anser); 55 } 56 } 57 } 58 return 0; 59 }

?第二種寫法：奇葩錯誤，少了個M--

1 #include<algorithm> 2 using namespace std; 3 #include<stdio.h> 4 #include<string.h> 5 const int INF=0x3f3f3f3f; 6 const int MAXN=200010; 7 #define lson root<<1,l,mid 8 #define rson root<<1|1,mid+1,r 9 #define L tree[root].l 10 #define R tree[root].r 11 #define V tree[root].v 12 #define NOW tree[root].v=MAX(tree[root<<1].v,tree[root<<1|1].v) 13 //#define LOCAL 14 int MAX(int x,int y){ 15 return x>y?x:y; 16 } 17 struct Node{ 18 int l,r,v; 19 }; 20 Node tree[MAXN<<2]; 21 int ans; 22 void build(int root,int l,int r){ 23 L=l;R=r; 24 if(l==r){ 25 scanf("%d",&V); 26 } 27 else{ 28 int mid=(l+r)>>1; 29 build(lson); 30 build(rson); 31 NOW; 32 } 33 } 34 void update(int root,int x,int y){ 35 if(L==x&&R==x){ 36 V=y; 37 } 38 else{ 39 int mid=(L+R)>>1; 40 if(mid>=x)update(root<<1,x,y); 41 else update(root<<1|1,x,y); 42 NOW; 43 } 44 } 45 void query(int root,int x,int y){ 46 if(L>=x&&R<=y){ 47 ans=MAX(ans,V); 48 } 49 else { 50 int mid=(L+R)>>1; 51 if(mid>=x)query(root<<1,x,y); 52 if(mid<y)query(root<<1|1,x,y); 53 } 54 } 55 int main(){ 56 #ifdef LOCAL 57 freopen("data.in","r",stdin); 58 freopen("data.out","w",stdout); 59 #endif 60 int N,M; 61 char s[5]; 62 int a,b; 63 while(~scanf("%d%d",&N,&M)){ 64 build(1,1,N); 65 while(M--){ 66 scanf("%s%d%d",s,&a,&b); 67 if(s[0]=='U'){ 68 update(1,a,b); 69 } 70 else{ 71 ans=0; 72 if(a>b)swap(a,b); 73 query(1,a,b); 74 printf("%d\n",ans); 75 } 76 } 77 } 78 return 0; 79 }

?

總結

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

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