POJ 2155 Matrix ( 二维树状数组 ) || HDU 3584 Cube ( 三维树状数组 )

举报
Linux猿 发表于 2021/08/06 00:53:38 2021/08/06
【摘要】 题目链接~~> 做题感悟:这题只要把一维的树状数组扩展到二维就可以了。 解题思路:树状数组插线问点:先简化一下,如果是一维的树状数组的插线问点让区间 [ a,b ] 同时加 x ,可以先让 [ 1,b ] + 1 ,再让 [ 1 ,a-1 ] -1 ,跟前缀和一样这样区间 [ a,b ] 就实现了 +1 ,但这时数组 c [ ]&nbs...

题目链接~~>

做题感悟:这题只要把一维的树状数组扩展到二维就可以了。

解题思路:树状数组插线问点:先简化一下,如果是一维的树状数组的插线问点让区间 [ a,b ] 同时加 x ,可以先让 [ 1,b ] + 1 ,再让 [ 1 ,a-1 ] -1 ,跟前缀和一样这样区间 [ a,b ] 就实现了 +1 ,但这时数组 c [ ] 代表是它管辖范围内每个点的值为  c [  ] ( 此时c 数组的意义已经变了,不再代表所管辖区间的和) .

 很明显如果查询某个点的值需要取所有管辖它的区间的和。好了,现在我们可以考虑这个题了,假设 改变矩形 ( x1 , y1 )  ~ ( x2 , y2 ) 就可以让 ( 1 , 1 )  ~ ( x2 , y2 ) 同时 + 1 ,让( 1 , 1 )  ~ ( x1-1 , y1-1 ) 同时  - 1 ,让( 1 , 1 )  ~ ( x1-1 , y2) 同时 - 1 ,让( 1 , 1 )  ~ ( x2 , y1-1 ) 同时 - 1,查询时和一维数组类似,如果是偶数代表 0 奇数代表 1 . ( 这里有一个小规律,总是让出现 x1 , y1 时减一就可以了)      

代码(POJ 2155):


  
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<map>
  4. #include<stack>
  5. #include<string>
  6. #include<string.h>
  7. #include<stdlib.h>
  8. #include<math.h>
  9. #include<vector>
  10. #include<queue>
  11. #include<algorithm>
  12. using namespace std ;
  13. #define LEN sizeof(struct node)
  14. #define lld __int64
  15. const double PI = 3.1415926535898 ;
  16. const int INF = 99999999 ;
  17. const double esp = 1e-8 ;
  18. const long long mod= 1000 ;
  19. const int MX = 1005 ;
  20. int n ;
  21. int c[MX][MX] ;
  22. int lowbit(int x)
  23. {
  24. return x & (-x) ;
  25. }
  26. int get_su(int x,int y) // 求值
  27. {
  28. int ans=0,y1 ;
  29. while(x<=n)
  30. {
  31. y1=y ;
  32. while(y1<=n)
  33. {
  34. ans+=c[x][y1] ;
  35. y1+=lowbit(y1) ;
  36. }
  37. x+=lowbit(x) ;
  38. }
  39. return ans ;
  40. }
  41. void add(int x,int y,int num) // 更新
  42. {
  43. int y1 ;
  44. while(x>0)
  45. {
  46. y1=y ;
  47. while(y1>0)
  48. {
  49. c[x][y1]+=num ;
  50. y1-=lowbit(y1) ;
  51. }
  52. x-=lowbit(x) ;
  53. }
  54. }
  55. int main()
  56. {
  57. char s[10] ;
  58. int Tx,m,x,y,x1,y1 ;
  59. scanf("%d",&Tx) ;
  60. while(Tx--)
  61. {
  62. scanf("%d%d",&n,&m) ;
  63. memset(c,0,sizeof(c)) ;
  64. for(int i=1 ;i<=m ;i++)
  65. {
  66. scanf("%s",s) ;
  67. scanf("%d%d",&x,&y) ;
  68. if(s[0]=='C')
  69. {
  70. scanf("%d%d",&x1,&y1) ;
  71. add(x1,y1,1) ;
  72. add(x-1,y-1,1) ;
  73. add(x1,y-1,-1) ;
  74. add(x-1,y1,-1) ;
  75. }
  76. else
  77. printf("%d\n",get_su(x,y)%2) ;
  78. }
  79. if(Tx) printf("\n") ;
  80. }
  81. return 0 ;
  82. }

HDU 3584 和二维的差不多,但是更新很麻烦,不多说了看代码。

代码:


  
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<map>
  4. #include<stack>
  5. #include<string>
  6. #include<string.h>
  7. #include<stdlib.h>
  8. #include<math.h>
  9. #include<vector>
  10. #include<queue>
  11. #include<algorithm>
  12. using namespace std ;
  13. #define LEN sizeof(struct node)
  14. #define lld __int64
  15. const double PI = 3.1415926535898 ;
  16. const int INF = 99999999 ;
  17. const double esp = 1e-8 ;
  18. const long long mod= 1000 ;
  19. const int MX = 105 ;
  20. int n ;
  21. int c[MX][MX][MX] ;
  22. int lowbit(int x)
  23. {
  24. return x&(-x) ;
  25. }
  26. int get_su(int x,int y,int z)// 求和
  27. {
  28. int y1,z1,ans=0 ;
  29. while(x<=n)
  30. {
  31. y1=y ;
  32. while(y1<=n)
  33. {
  34. z1=z ;
  35. while(z1<=n)
  36. {
  37. ans+=c[x][y1][z1] ;
  38. z1+=lowbit(z1) ;
  39. }
  40. y1+=lowbit(y1) ;
  41. }
  42. x+=lowbit(x) ;
  43. }
  44. return ans ;
  45. }
  46. void add(int x,int y,int z,int num)// 更新
  47. {
  48. int y1,z1 ;
  49. while(x>0)
  50. {
  51. y1=y ;
  52. while(y1>0)
  53. {
  54. z1=z ;
  55. while(z1>0)
  56. {
  57. c[x][y1][z1]+=num ;
  58. z1-=lowbit(z1) ;
  59. }
  60. y1-=lowbit(y1) ;
  61. }
  62. x-=lowbit(x) ;
  63. }
  64. }
  65. int main()
  66. {
  67. int m,x,y,z,x1,y1,z1,ch ;
  68. while(~scanf("%d%d",&n,&m))
  69. {
  70. memset(c,0,sizeof(c)) ;
  71. for(int i=0 ;i<m ;i++)
  72. {
  73. scanf("%d%d%d%d",&ch,&x,&y,&z) ;
  74. if(ch)
  75. {
  76. scanf("%d%d%d",&x1,&y1,&z1) ;
  77. add(x1,y1,z1,1) ; // 只要将 出现x ,y ,z的坐标统统减一就 ok
  78. add(x-1,y1,z-1,1) ; // 其实可以全更新 1 不用更新 -1 道理一样
  79. add(x-1,y1,z1,-1) ;
  80. add(x1,y1,z-1,-1) ;
  81. add(x1,y-1,z1,-1) ;
  82. add(x-1,y-1,z-1,-1) ;
  83. add(x-1,y-1,z1,1) ;
  84. add(x1,y-1,z-1,1) ;
  85. }
  86. else
  87. printf("%d\n",get_su(x,y,z)%2) ;
  88. }
  89. }
  90. return 0 ;
  91. }



 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/22882383

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。