fork(1) download
  1. //============================================================================
  2. // Name : SPOJ Multiple by 3 (Segment Tree)
  3. // Author : Tarango Khan
  4. // Copyright : Team Byteheads
  5. // Description : !!!Hello World!!!
  6. //============================================================================
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. #define Size 100005
  11.  
  12. struct vert{
  13. int cnt[3];
  14. int prop;
  15. };
  16. vert tree[Size*4];
  17.  
  18. void build_tree(int cur,int Start,int End){
  19. if(Start == End){
  20. tree[cur].cnt[0] = 1;
  21. tree[cur].cnt[1] = 0;
  22. tree[cur].cnt[2] = 0;
  23. tree[cur].prop = 0;
  24. return;
  25. }
  26. int left = cur*2;
  27. int right = left+1;
  28. int mid = (Start+End)/2;
  29. build_tree(left,Start,mid);
  30. build_tree(right,mid+1,End);
  31. tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
  32. tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
  33. tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
  34. tree[cur].prop = tree[left].prop + tree[right].prop;
  35. }
  36.  
  37. void update_prop(int cur){
  38. int tmp = tree[cur].cnt[2];
  39. tree[cur].cnt[2] = tree[cur].cnt[1];
  40. tree[cur].cnt[1] = tree[cur].cnt[0];
  41. tree[cur].cnt[0] = tmp;
  42. }
  43.  
  44. void update_child(int cur,int left,int right){
  45. tree[left].prop += tree[cur].prop;
  46. tree[right].prop += tree[cur].prop;
  47. int rotate = tree[cur].prop%3;
  48. for(int s = 0;s<rotate;s++){
  49. update_prop(left);
  50. update_prop(right);
  51. }
  52. tree[cur].prop = 0;
  53. }
  54.  
  55. void update_tree(int cur,int Start,int End,int u,int v){
  56. if(Start == u && End == v){
  57. tree[cur].prop += 1;
  58. update_prop(cur);
  59. return;
  60. }
  61. int left = cur*2;
  62. int right = left+1;
  63. int mid = (Start+End)/2;
  64.  
  65. if(tree[cur].prop != 0){ //If prop exist then we add that to his child and make his one to 0;
  66. update_child(cur,left,right);
  67. }
  68.  
  69. if(v <= mid){
  70. update_tree(left,Start,mid,u,v);
  71. }else if(u > mid){
  72. update_tree(right,mid+1,End,u,v);
  73. }else{
  74. update_tree(left,Start,mid,u,mid);
  75. update_tree(right,mid+1,End,mid+1,v);
  76. }
  77. tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
  78. tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
  79. tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
  80. }
  81.  
  82. int tree_query(int cur,int Start,int End,int u,int v){
  83. if(Start == u && End == v){
  84. return tree[cur].cnt[0];
  85. }
  86. int left = cur*2;
  87. int right = left+1;
  88. int mid = (Start+End)/2;
  89. if(tree[cur].prop != 0){ //If prop exist then we add that to his child and make his one to 0;
  90. update_child(cur,left,right);
  91. }
  92. if(v <= mid){
  93. return tree_query(left,Start,mid,u,v);
  94. }else if(u > mid){
  95. return tree_query(right,mid+1,End,u,v);
  96. }else{
  97. return tree_query(left,Start,mid,u,mid) + tree_query(right,mid+1,End,mid+1,v);
  98. }
  99. }
  100.  
  101. int main() {
  102. int N,Q,u,v,type;
  103. scanf("%d %d",&N,&Q);
  104. build_tree(1,1,N);
  105. for(int i = 1;i<=Q;i++){
  106. scanf("%d",&type);
  107. if(type == 0){
  108. scanf("%d %d",&u,&v);
  109. u++;v++;
  110. update_tree(1,1,N,u,v);
  111. }else{
  112. scanf("%d %d",&u,&v);
  113. u++;v++;
  114. int sum = tree_query(1,1,N,u,v);
  115. printf("%d\n",sum);
  116. }
  117. }
  118. return 0;
  119. }
  120.  
Success #stdin #stdout 0s 9392KB
stdin
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
4
1
0
2