简单线段树的单点更新..
这题有点坑..用宏定义会超时..不懂为什么..
1 #include <iostream> 2 #include <string.h> 3 #define maxn 200005 4 //#define max(a,b) a>b?a:b 5 int segment[maxn<<2]; 6 int N,M; 7 int max(int a,int b){ 8 return a>b?a:b; 9 } 10 void pushUp(int rt){ 11 segment[rt] = max(segment[rt<<1],segment[rt<<1|1]); 12 } 13 void buildTree(int left,int right,int rt){ 14 if(left == right){ 15 scanf("%d",segment+rt); 16 return ; 17 } 18 int mid = (left + right ) >> 1; 19 buildTree(left,mid,rt<<1); 20 buildTree(mid+1,right,rt<<1|1); 21 pushUp(rt); 22 } 23 24 void update(int rt,int index,int value,int left,int right){ 25 if(left == right ){ 26 segment[rt] = value; 27 return ; 28 } 29 int mid = (left + right ) >> 1; 30 if(mid >= index) 31 update(rt<<1,index,value,left,mid); 32 else 33 update(rt<<1|1,index,value,mid+1,right); 34 pushUp(rt); 35 } 36 //拆分区间,直至找到子区间; 37 int query(int left,int right,int rt,int L,int R){ 38 if(left >= L && right <= R){ 39 return segment[rt]; 40 } 41 int mid = (left + right) >> 1; 42 int max_num = -1; 43 if( L <= mid){ 44 max_num = max(max_num,query(left,mid,rt<<1,L,R)); 45 } 46 if( R > mid){ 47 max_num = max(max_num,query(mid+1,right,rt<<1|1,L,R)); 48 } 49 return max_num; 50 } 51 int main() 52 { 53 char op[2]; 54 int A,B; 55 while(scanf("%d %d",&N,&M)!=EOF){ 56 buildTree(1,N,1); 57 for(int i = 0 ; i < M ; i++){ 58 scanf("%s%d%d",op,&A,&B); 59 if(op[0]=='Q') 60 printf("%d ",query(1,N,1,A,B)); 61 else 62 update(1,A,B,1,N); 63 } 64 } 65 return 0; 66 }