树状数组

浏览数：14 / 时间：2015年06月08日 
  1. #include <vector>
  2. #include <queue>
  3. #include <stack>
  4. #include <set>
  5. #include <map>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <stdio.h>
  9. #include <string.h>
  10. using namespace std;
  12. #define MAXN 200020
  13. #define MAX(a,b) (a>b?a:b)
  14. #define Lowbit(x) (x & (-x))
  16. int num[MAXN]={0,3,1,2,4,5,8,7,9,6};//注意从下标为1的位置开始保存数据
  17. int C[MAXN];
  21. int Query(int l,int r){
  22. 	int ans=num[r];
  23. 	while(true){
  24. 		ans=MAX(ans,num[r]);
  25. 		if(r==l) break;
  26. 		for(r-=1;r-l>=Lowbit(r);r-=Lowbit(r)){
  27. 			ans=MAX(ans,C[r]);
  28. 		}
  29. 	}
  30. 	return ans;
  31. }
  33. void Modify(int p,int val,int end){
  34. 	num[p]=val;
  35. 	for(int i=p;i<=end;i+=Lowbit(i)){
  36. 		C[i]=val;
  37. 		for(int j=1;j<Lowbit(i);j<<=1){
  38. 			C[i]=MAX(C[i],C[i-j]);
  39. 		}
  40. 	}
  41. }
  43. int main(int argc, char *argv[])
  44. {
  46. 	int n,m;
  47. 	char op[3];
  48. 	int s,e;
  49. 	while(scanf("%d%d",&n,&m)!=EOF){
  50. 		memset(C,0,sizeof(C));
  51. 		memset(num,0,sizeof(num));
  53. 		for(int i=1;i<=n;i++){
  54. 			scanf("%d",&num[i]);
  55. 			Modify(i,num[i],n);
  56. 		}
  57. 		while(m--){
  58. 			scanf("%s%d%d",op,&s,&e);
  59. 			if(op[0]==‘Q‘)
  60. 				printf("%d\n",Query(s,e));
  61. 			else
  62. 				Modify(s,e,n);
  63. 		}
  65. 	}
  66. }





附件列表

     

    郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

    标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

    相关文章

    随机文章

    您可能还喜欢

    您可能还喜欢