fork(1) download
copy 
  1. #include<string.h>
  2. #define MAX 1000000
  3. #include<stdio.h>
  4. struct abc
  5. {
  6. 	int zero,one,two,flip;	//flip for lazy propagation; one two zero are elements leaving 1,2,0 as remainder when divided by 3
  7. }tree[MAX];
  8. void build(int node,int left,int right)
  9. {
  10. 	if(left==right)
  11. 	{
  12. 		tree[node].zero=1;	//initially elements are zero, 
  13. 		tree[node].one=0;
  14. 		tree[node].two=0;
  15. 		tree[node].flip=0;
  16. 		return;
  17. 	}
  18. 	int mid=left+right;
  19. 	mid/=2;
  20. 	build(2*node,left,mid);
  21. 	build(2*node+1,mid+1,right);
  22. 	tree[node].zero=tree[2*node].zero+tree[2*node+1].zero;	//Rest are zero initially, except this field
  23. 	tree[node].one=0;
  24. 	tree[node].two=0;
  25. 	tree[node].flip=0;
  26. }
  27. void update(int node,int left,int right,int i,int j)
  28. {
  29. 	if(tree[node].flip!=0)		//We need to flip once, twice or zero times
  30. 	{
  31. 		int temp=tree[node].one;
  32. 		tree[node].one=tree[node].zero;
  33. 		tree[node].zero=tree[node].two;
  34. 		tree[node].two=temp;
  35.  
  36. 		if(tree[node].flip==2)	//If one flip, it is done above. For two flips, the swapping is done again
  37. 		{
  38. 			int temp=tree[node].one;
  39. 			tree[node].one=tree[node].zero;
  40. 			tree[node].zero=tree[node].two;
  41. 			tree[node].two=temp;
  42. 		}
  43. 		if(i!=j)		//Children flip count is incremented, modulo 3 to find number of swapping step required
  44. 		{
  45. 			tree[2*node].flip+=1;
  46. 			tree[2*node+1].flip+=1;
  47. 			tree[2*node].flip%=3;
  48. 			tree[2*node+1].flip%=3;
  49. 		}
  50. 		tree[node].flip=0;
  51. 	}
  52. 	if(i>right || j<left)	//out of bound
  53. 		return;
  54. 	if(i>=left && j<=right)
  55. 	{
  56. 		int temp=tree[node].one;
  57. 		tree[node].one=tree[node].zero;
  58. 		tree[node].zero=tree[node].two;
  59. 		tree[node].two=temp;
  60. 		if(i!=j)
  61. 		{
  62. 			tree[2*node].flip+=1;
  63. 			tree[2*node+1].flip+=1;
  64. 			tree[2*node].flip%=3;
  65. 			tree[2*node+1].flip%=3;
  66. 		}
  67. 		return;
  68. 	}
  69. 	int mid=i+j;
  70. 	mid/=2;
  71. 	update(2*node,left,right,i,mid);
  72. 	update(2*node+1,left,right,mid+1,j);
  73. 	tree[node].zero=tree[2*node].zero+tree[2*node+1].zero;
  74. 	tree[node].one=tree[2*node].one+tree[2*node+1].one;
  75. 	tree[node].two=tree[2*node].two+tree[2*node+1].two;
  76. }
  77. int query(int node,int left,int right,int i,int j)
  78. {
  79. 	if(i>right || j<left)
  80. 		return 0;
  81. 	if(tree[node].flip!=0)
  82. 	{
  83. 		int temp=tree[node].one;
  84. 		tree[node].one=tree[node].zero;
  85. 		tree[node].zero=tree[node].two;
  86. 		tree[node].two=temp;
  87. 		if(tree[node].flip==2)
  88. 		{
  89. 			int temp=tree[node].one;
  90. 			tree[node].one=tree[node].zero;
  91. 			tree[node].zero=tree[node].two;
  92. 			tree[node].two=temp;
  93. 		}
  94. 		if(i!=j)
  95. 		{
  96. 			tree[2*node].flip+=1;
  97. 			tree[2*node+1].flip+=1;
  98. 			tree[2*node].flip%=3;
  99. 			tree[2*node+1].flip%=3;
  100. 		}
  101. 		tree[node].flip=0;
  102. 	}
  103. 	if(i>=left && j<=right)
  104. 		return tree[node].zero;
  105. 	int mid=i+j;
  106. 	mid/=2;
  107. 	int a=query(2*node,left,right,i,mid);
  108. 	int b=query(2*node+1,left,right,mid+1,j);
  109. 	return a+b;
  110. }
  111. int main()
  112. {
  113. 	int n,q;
  114. 	scanf("%d%d",&n,&q);
  115. 	build(1,0,n-1);
  116. 	while(q--)
  117. 	{
  118. 		int a,b,c;
  119. 		scanf("%d%d%d",&a,&b,&c);
  120. 		if(a)
  121. 		{
  122. 			printf("%d\n",query(1,b,c,0,n-1));
  123. 		}
  124. 		else
  125. 		{
  126. 			update(1,b,c,0,n-1);
  127. 		}
  128. 	}
  129. }
Success #stdin #stdout 0s 17792KB
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/XeaRbB
language:
C99 (gcc 8.3)
created:
8 years ago
visibility:
public

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!