fork download
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string.h>
  5. #include <stdbool.h>
  6. #include <math.h>
  7. #define ll long long int
  8. #define MAX 100000+10
  9. #define ull unsigned long long int
  10. #define gcd(a,b) __gcd(a,b)
  11.  
  12. using namespace std;
  13.  
  14. struct info
  15. {
  16. int zero,one,two,lazy;
  17. } tree[MAX*5];
  18.  
  19. void update_lazy(int node)
  20. {
  21. int temp = tree[node].zero;
  22. tree[node].zero = tree[node].two;
  23. tree[node].two = tree[node].one;
  24. tree[node].one = temp;
  25. }
  26.  
  27. void update_node(int node,int left)
  28. {
  29. tree[left].lazy += tree[node].lazy;
  30. tree[left+1].lazy += tree[node].lazy;
  31.  
  32. tree[node].lazy%=3;
  33. int shift = tree[node].lazy;
  34. while(shift--)
  35. {
  36. update_lazy(left);
  37. update_lazy(left+1);
  38. }
  39. tree[node].lazy=0;
  40. }
  41.  
  42. void marge(int node, int left, int right)
  43. {
  44. tree[node].zero= tree[left].zero + tree[right].zero;
  45. tree[node].one= tree[left].one + tree[right].one;
  46. tree[node].two= tree[left].two + tree[right].two;
  47. }
  48.  
  49. void build(int node, int b, int e)
  50. {
  51. if (b == e)
  52. {
  53. tree[node].one = 0;
  54. tree[node].two = 0;
  55. tree[node].lazy = 0;
  56. tree[node].zero = 1;
  57.  
  58. return;
  59. }
  60. int Left = node * 2;
  61. int Right = node * 2 + 1;
  62. int mid = (b + e) / 2;
  63. build(Left, b, mid);
  64. build(Right, mid + 1, e);
  65.  
  66. marge(node,Left,Right);
  67.  
  68. }
  69.  
  70. void update(int node, int l, int r, int i, int j)
  71. {
  72. //cout<<node<<" "<<l<<" "<<r<<" "<<i<<" "<<j<<endl;
  73. int Left = node*2;
  74. if(tree[node].lazy!=0){
  75. update_node(node,Left);
  76. }
  77. //no overlap
  78. if(l>r || l>j || r<i) return;
  79.  
  80. //total overlap
  81. if(l>=i && r<=j){
  82. tree[node].lazy++;
  83. update_lazy(node);
  84. return;
  85. }
  86. //partial overlap
  87. int mid = (l+r)/2;
  88. update(Left,l,mid,i,j);
  89. update(Left+1,mid+1,r,i,j);
  90.  
  91. marge(node,Left,Left+1);
  92.  
  93. }
  94.  
  95. int query(int node,int l,int r,int i,int j)
  96. {
  97. if(l>r || l>j || r<i) return 0;
  98. if(tree[node].lazy!=0){
  99.  
  100. update_node(node,node*2);
  101. }
  102. if(l>=i && r<=j) return tree[node].zero;
  103. int mid = (l+r)/2;
  104. int Left = node*2;
  105. return query(Left,l,mid,i,j) + query(Left+1,mid+1,r,i,j);
  106. }
  107.  
  108. int main()
  109. {
  110. int t,no=0;
  111. // scanf("%d",&t);
  112.  
  113. // while(t--)
  114. {
  115. int n,q,a;
  116. scanf("%d %d",&n,&q);
  117.  
  118. memset(tree,0,sizeof(tree));
  119. build(1,1,n);
  120.  
  121. printf("Case %d:\n",++no);
  122. while(q--)
  123. {
  124. int type,l,r;
  125. scanf("%d %d %d",&type,&l,&r);
  126. l++;
  127. r++;
  128.  
  129. if(type == 0)
  130. {
  131. update(1,1,n,l,r);
  132. }
  133. else
  134. {
  135. printf("%d\n",query(1,1,n,l,r));
  136. }
  137. }
  138. }
  139.  
  140. return 0;
  141. }
  142.  
Success #stdin #stdout 0s 5020KB
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
Case 1:
4
1
0
2