首页 > 代码库 > hdu 1754 树状数组求最大值

hdu 1754 树状数组求最大值

  1. #include <stdio.h>
  2. #include <string>
  3. #define MAX(a,b) (a>b?a:b)
  4. #define Lowbit(x) (x & (-x))
  5. int idx[200010], num[200010];
  6. /*int Lowbit(int x)
  7. {
  8. return x&(-x);
  9. }*/
  10. /*int MAX(int x, int y)
  11. {
  12. return x > y ? x:y;
  13. }*/
  14. /*
  15. 对于区间 [l,r] 把该区间转化为多个的小区间再进行求最值,
  16. 方法是从后往前对每一个索引数的范围进行判断, 如在进行到第k项时,
  17. 该数控制的范围是 [k-Lowbit(k)+1,k], 如果k-Lowbit(k)+1在所求的范围内的话则将该区间的最值加入最值的判断,
  18. 然后转至地k-Lowbit(k),否则的话就只对第k个数进行最值判断,然后转至k-1
  19. */
  20. int Query(int l,int r)
  21. {
  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. {
  28. ans=MAX(ans,idx[r]);
  29. }
  30. }
  31. return ans;
  32. }
  33. /*约定以 num[] 表示原数组, 以 idx[] 表示索引数组, Lowbit(x)=x&(-x)
  34. 树状数组求和时通过构造数组 idx[] 使 idx[k]=sum(num[tk]), tk [k-Lowbit(k)+1,k], 使用同样的方法构造最值索引数组:
  35. 以最大值为例, 先讨论询问过程中不对数组做任何修改的情况, 用 idx[k] 记录 [k-Lowbit(k)+1,k] 区间内的最大值 */
  36. void Modify(int id,int grade,int n)
  37. {
  38. num[id] = grade;
  39. for(int i = id;i<=n;i+=Lowbit(i)){
  40. idx[i] = grade;
  41. for(int j=1;j<Lowbit(i);j<<=1){
  42. idx[i]=MAX(idx[i],idx[i-j]);
  43. }
  44. }
  45. }
  46. int main()
  47. {
  48. int n,m;
  49. while( scanf("%d %d", &n, &m)!=EOF )
  50. {
  51. memset(idx, 0, sizeof(idx) );
  52. memset(num, 0, sizeof(num) );
  53. for(int i=1; i<=n; i++) //i 为 id 即第几个人
  54. {
  55. scanf("%d", &num[i]);
  56. Modify(i, num[i], n); //一定要从1开始建立, 参数需建立数组, 为了改变idx
  57. }
  58. while(m--)
  59. {
  60. char str[3];
  61. int light, right;
  62. scanf("%s%d%d",str, &light, &right);
  63. if( str[0] == ‘Q‘ )
  64. printf("%d\n", Query(light, right) );
  65. else
  66. Modify(light, right, n); //这里代表更换的id的grade
  67. }
  68. }
  69. return 0;
  70. }
  71. /*
  72. 本题目包含多组测试,请处理到文件结束。
  73. 在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
  74. 学生ID编号分别从1编到N。
  75. 第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
  76. 接下来有M行。每一行有一个字符 C (只取‘Q‘或‘U‘) ,和两个正整数A,B。
  77. 当C为‘Q‘的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
  78. 当C为‘U‘的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
  79. Output
  80. 对于每一次询问操作,在一行里面输出最高成绩。
  81. Sample Input
  82. 5 6
  83. 1 2 3 4 5
  84. Q 1 5
  85. U 3 6
  86. Q 3 4
  87. Q 4 5
  88. U 2 9
  89. Q 1 5
  90. Sample Output
  91. 5
  92. 6
  93. 5
  94. 9
  95. */



来自为知笔记(Wiz)


附件列表

     

    hdu 1754 树状数组求最大值