fork download
copy 
  1. #include<stdio.h>
  2. struct seg
  3. {
  4. 	int a,b,c;		//a = div by three, b = remainder 1 c = remainder 2
  5. }tree[1000000];
  6. void create(int node, int left, int right)
  7. {
  8. 	if(left>right)
  9. 		return;
  10. 	if(left==right)
  11. 	{
  12. 		tree[node].a=1;		//As at time of creation, initial value is zero, divisible by 3
  13. 		tree[node].b=0;
  14. 		tree[node].c=0;
  15. 		return;
  16. 	}
  17. 	int mid=(left+right)/2;
  18. 	create(2*node,left,mid);
  19. 	create(2*node+1,mid+1,right);
  20.  
  21. 	tree[node].a=tree[2*node].a+tree[2*node+1].a;		
  22. 	tree[node].b=tree[2*node].b+tree[2*node+1].b;
  23. 	tree[node].c=tree[2*node].c+tree[2*node+1].c;
  24. }
  25. int query(int node,int left, int right, int i, int j)
  26. {
  27. 	if(left>right)
  28. 		return 0;
  29. 	if(left>j || right<i)
  30. 		return 0;
  31. 	if(left >= i && right <= j)
  32. 		return tree[node].a;
  33. 	int mid=left+right;
  34. 	mid/=2;
  35. 	return query(2*node,left,mid,i,j)+query(2*node+1,mid+1,right,i,j);
  36. }
  37. void update(int node, int left, int right, int i, int j)
  38. {
  39. 	if(left>right)
  40. 		return;
  41. 	if(left>j || right<i)
  42. 		return;
  43. 	if(left >= i && right <= j)
  44. 	{
  45. 		int temp=tree[node].a;
  46. 		tree[node].a=tree[node].b;
  47. 		tree[node].b=tree[node].c;
  48. 		tree[node].c=temp;
  49. 		return;
  50. 	}
  51. 	int mid=left+right;
  52. 	mid/=2;
  53. 	update(2*node,left,mid,i,j);
  54. 	update(2*node+1,mid+1,right,i,j);
  55. }
  56. int main()
  57. {
  58. 	int n,a,b,q,choice;
  59. 	scanf("%d%d",&n,&q);
  60. 	create(1,0,n-1);
  61. 	while(q--)
  62. 	{
  63. 		scanf("%d%d%d",&choice,&a,&b);
  64. 		if(choice)
  65. 		{
  66. 			printf("%d\n",query(1,0,n-1,a+1,b+1));
  67. 		}
  68. 		else
  69. 			update(1,0,n-1,a+1,b+1);
  70. 	}
  71. }
Success #stdin #stdout 0s 13776KB
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 
3
1
0
2
https://ideone.com/PYYJHH
language:
C99 (gcc 8.3)
created:
8 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!