fork download
copy 
  1. //MULTQ3 - Multiples of 3
  2. # include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. # define  mod 	     1000000007
  6. # define  ll	     long long
  7. # define  INF	     1e18
  8. # define  mp         make_pair
  9. # define  pb         push_back
  10. # define  fill(a,v)  memset(a, v, sizeof a)
  11.  
  12. ll N,Q;
  13. struct data
  14. {
  15. 	ll zeros;
  16. 	ll ones;
  17. 	ll twos;
  18. };
  19. data tree[4*123456];
  20. ll lazy[4*123456];
  21. ll ch,L,R;
  22. void build(ll node,ll start,ll end)
  23. {
  24. 	if(start!=end)
  25. 	{
  26. 		ll mid=(start+end)/2;
  27. 		build(2*node,start,mid);
  28. 		build(2*node+1,mid+1,end);
  29. 		tree[node].zeros=tree[2*node].zeros+tree[2*node+1].zeros;
  30. 		tree[node].ones=tree[2*node].ones+tree[2*node+1].ones;
  31. 		tree[node].twos=tree[2*node].twos+tree[2*node+1].twos;
  32. 	}
  33. 	else
  34. 	{
  35. 		tree[node].zeros=1;
  36. 		tree[node].ones=tree[node].twos=0;
  37. 	}/*
  38. 	cout<<start<<":"<<end<<"::"<<endl;
  39. 	cout<<"	"<<"zeros:"<<tree[node].zeros<<endl;
  40. 	cout<<"	"<<"ones:"<<tree[node].ones<<endl;
  41. 	cout<<"	"<<"twos:"<<tree[node].twos<<endl;*/
  42. }
  43.  
  44. void update(ll node,ll start,ll end)
  45. {
  46. 	if(lazy[node]!=0)
  47. 	{
  48.  
  49. 		lazy[2*node]+=lazy[node];
  50. 		lazy[2*node+1]+=lazy[node];
  51. 		lazy[node]%=3;
  52. 		ll temp0=tree[node].zeros;
  53. 		ll temp1=tree[node].ones;
  54. 		ll temp2=tree[node].twos;
  55. 		if(lazy[node]==1)
  56. 		{
  57. 			tree[node].zeros=temp2;
  58. 			tree[node].ones=temp0;
  59. 			tree[node].twos=temp1;
  60. 		}
  61. 		else if(lazy[node]==2)
  62. 		{
  63. 			tree[node].zeros=temp1;
  64. 			tree[node].ones=temp2;
  65. 			tree[node].twos=temp0;
  66. 		}
  67. 		lazy[node]=0;
  68. 	}
  69. 	if(L>end || R<start)
  70. 		return;
  71. 	else if(L<=start && R>=end)//inside
  72. 	{
  73. 		lazy[2*node]++;
  74. 		lazy[2*node+1]++;
  75. 		ll temp0=tree[node].zeros;
  76. 		ll temp1=tree[node].ones;
  77. 		ll temp2=tree[node].twos;
  78. 		tree[node].zeros=temp2;
  79. 		tree[node].ones=temp0;
  80. 		tree[node].twos=temp1;
  81. 	}
  82. 	else
  83. 	{
  84. 		ll mid=(start+end)/2;
  85. 		update(2*node,start,mid);
  86. 		update(2*node+1,mid+1,end);
  87. 		tree[node].zeros=tree[2*node].zeros+tree[2*node+1].zeros;
  88. 		tree[node].ones=tree[2*node].ones+tree[2*node+1].ones;
  89. 		tree[node].twos=tree[2*node].twos+tree[2*node+1].twos;
  90. 	}
  91. /*
  92. 	cout<<start<<":"<<end<<"::"<<endl;
  93. 	cout<<"	"<<"zeros:"<<tree[node].zeros<<endl;
  94. 	cout<<"	"<<"ones:"<<tree[node].ones<<endl;
  95. 	cout<<"	"<<"twos:"<<tree[node].twos<<endl;*/
  96. }
  97. data query(ll node,ll start,ll end)
  98. {
  99. 	data temp;
  100. 	if(lazy[node]!=0)
  101. 	{
  102.  
  103. 		lazy[2*node]+=lazy[node];
  104. 		lazy[2*node+1]+=lazy[node];
  105. 		lazy[node]%=3;
  106. 		ll temp0=tree[node].zeros;
  107. 		ll temp1=tree[node].ones;
  108. 		ll temp2=tree[node].twos;
  109. 		if(lazy[node]==1)
  110. 		{
  111. 			tree[node].zeros=temp2;
  112. 			tree[node].ones=temp0;
  113. 			tree[node].twos=temp1;
  114. 		}
  115. 		else if(lazy[node]==2)
  116. 		{
  117. 			tree[node].zeros=temp1;
  118. 			tree[node].ones=temp2;
  119. 			tree[node].twos=temp0;
  120. 		}
  121. 		lazy[node]=0;
  122. 	}
  123. 	if(L>end || R<start)
  124. 	{
  125. 		temp.zeros=temp.ones=temp.twos=0;
  126. 		return temp;
  127. 	}
  128. 	else if(L<=start && R>=end)
  129. 		return tree[node];
  130. 	else
  131. 	{
  132. 		ll mid=(start+end)/2;
  133. 		data left=query(2*node,start,mid);
  134. 		data right=query(2*node+1,mid+1,end);
  135. 		temp.zeros=left.zeros+right.zeros;
  136. 		temp.ones=left.ones+right.ones;
  137. 		temp.twos=left.twos+right.twos;
  138. 		return temp;
  139. 	}
  140. }
  141. int main()
  142. {
  143. ll i,j;
  144. 	scanf("%lld%lld",&N,&Q);
  145. 	build(1,1,N);
  146. 	fill(lazy,0);
  147. 	while(Q--)
  148. 	{
  149. 		scanf("%lld%lld%lld",&ch,&L,&R);
  150. 		L++;
  151. 		R++;
  152. 		if(ch==1)
  153. 			printf("%lld\n",query(1,1,N).zeros);
  154. 		else
  155. 			update(1,1,N);
  156. 	}
  157. return 0;
  158. }
  159.  
  160.  
Success #stdin #stdout 0s 30672KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
copy 
4
1
0
2
https://ideone.com/Z4Z3n6
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!