Saleh127

Light OJ 1135

Jun 19th, 2021
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5. struct fun
  6. {
  7.  
  8. ll la=0,z=0,o=0,t=0;
  9.  
  10. } tree[402006];
  11. ll a[402005];
  12.  
  13. void swapp(ll node)
  14. {
  15. ll tmp=tree[node].z;
  16. tree[node].z=tree[node].t;
  17. tree[node].t=tree[node].o;
  18. tree[node].o=tmp;
  19. }
  20.  
  21. void treeconstruct(ll node,ll b,ll e)
  22. {
  23.  
  24. if(b==e)
  25. {
  26. tree[node].z+=1ll;
  27. return;
  28. }
  29.  
  30. ll left = node*2;
  31. ll right = node*2 + 1ll;
  32.  
  33. ll mid=(b+e)/2;
  34.  
  35. treeconstruct(left,b,mid);
  36. treeconstruct(right,mid+1,e);
  37.  
  38. tree[node].z=tree[left].z+tree[right].z;
  39.  
  40. }
  41.  
  42. ll queries(ll node,ll b,ll e,ll i,ll j,ll c)
  43. {
  44. if(i>e || j<b) return 0ll;
  45.  
  46. if(b>=i && e<=j)
  47. {
  48. if(c==0) return tree[node].z;
  49. else if(c==1) return tree[node].t;
  50. else return tree[node].o;
  51. }
  52.  
  53. ll left = node*2;
  54. ll right = node*2 + 1ll;
  55.  
  56. ll mid=(b+e)/2;
  57.  
  58. ll x=queries(left,b,mid,i,j,(c+tree[node].la)%3);
  59.  
  60. ll y=queries(right,mid+1,e,i,j,(c+tree[node].la)%3);
  61.  
  62. return x+y;
  63.  
  64. }
  65.  
  66. void update(ll node,ll b,ll e,ll i,ll j)
  67. {
  68.  
  69. if(i>e || j<b) return;
  70.  
  71. if(b>=i && e<=j)
  72. {
  73. swapp(node);
  74. tree[node].la++;
  75. tree[node].la%=3;
  76. return;
  77. }
  78.  
  79. ll left = node*2;
  80. ll right = node*2 + 1ll;
  81.  
  82. ll mid=(b+e)/2;
  83.  
  84. update(left,b,mid,i,j);
  85.  
  86. update(right,mid+1,e,i,j);
  87.  
  88. tree[node].z=tree[left].z+tree[right].z;
  89. tree[node].o=tree[left].o+tree[right].o;
  90. tree[node].t=tree[left].t+tree[right].t;
  91.  
  92. ll xx=tree[node].la;
  93.  
  94. if(xx)
  95. {
  96. while(xx--)
  97. {
  98. swapp(node);
  99. }
  100. }
  101. }
  102.  
  103. int main()
  104. {
  105. ios_base::sync_with_stdio(0);
  106. cin.tie(0);
  107. cout.tie(0);
  108.  
  109. test
  110. {
  111.  
  112. cout<<"Case "<<cs<<":"<<endl;
  113. ll q,n,m,i,j,k,l;
  114.  
  115. cin>>n>>q;
  116.  
  117. for(i=0; i<4*n; i++)
  118. {
  119. tree[i].la=tree[i].o=tree[i].t=tree[i].z=a[i]=0;
  120. }
  121.  
  122.  
  123. treeconstruct(1ll,1ll,n);
  124.  
  125. while(q--)
  126. {
  127. cin>>k>>j>>l;
  128.  
  129. if(k==0ll)
  130. {
  131. j++,l++;
  132. update(1ll,1ll,n,j,l);
  133. }
  134. else if(k==1ll)
  135. {
  136. j++,l++;
  137. m=queries(1ll,1ll,n,j,l,0ll);
  138. cout<<m<<endl;
  139. }
  140. }
  141.  
  142.  
  143. }
  144.  
  145. return 0;
  146. }
  147. /*
  148. 4 7
  149. 1 0 3
  150. 0 1 2
  151. 0 1 3
  152. 1 0 0
  153. 0 0 3
  154. 1 3 3
  155. 1 0 3
  156. */
  157.  
Advertisement
Add Comment
Please, Sign In to add comment