fork(1) download
copy 
  1. #include <iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4.  
  5. #define max 100001
  6.  
  7. int tree[4*max], a[max],val=1,lazy[max];
  8.  
  9. int __ch,__sign,h;
  10.  
  11. inline void S(  int &x )
  12. {
  13. 	x=0;
  14. 	while((__ch<'0' || __ch>'9') && __ch!='-' && __ch!=EOF)	__ch=getchar_unlocked();
  15. 	if (__ch=='-')
  16. 		__sign=-1 , __ch=getchar_unlocked();
  17. 	else
  18. 		__sign=1;
  19.  
  20. 	do
  21. 		x=(x<<3)+(x<<1)+__ch-'0';
  22. 	while((__ch=getchar_unlocked())>='0' && __ch<='9');
  23. 	x*=__sign;
  24. }
  25.  
  26. void build_tree(int node, int a[], int start, int end)
  27. {
  28. 	if(start==end)
  29. 	 {
  30. 	 	tree[node] = (a[start]%3==0?1:0);
  31. 	 	//cout<<" node is "<<node<<" : "<<tree[node]<<endl;
  32. 	 }
  33. 	else
  34. 	{
  35. 		int mid = (start+end)/2;
  36. 		build_tree(1+(2*node),a,start, mid);
  37. 		build_tree(2+(2*node), a, mid+1, end);
  38. 		tree[node] = tree[1+ 2*node] + tree[2+ 2*node];
  39. 	}
  40. }
  41.  
  42. int get_mul(int node, int start, int end, int l , int r)
  43. {
  44. 	if(start>=l && end<=r)
  45. 	 return tree[node];
  46.  
  47. 	if(l>end || start>r)
  48. 	 return 0;
  49.  
  50. 	int mid= (start+end)/2;
  51.  
  52. 	int p1= get_mul(1+ 2*node, start, mid, l,r);
  53. 	int p2= get_mul(2+ 2*node, mid+1, end, l,r);
  54. 	return p1+p2;
  55. }
  56.  
  57. void update(int node, int start, int end, int l, int r)
  58. {
  59. 	/*
  60. 	if(lazy[node]!=0)
  61. 	{
  62. 		tree[node]+=lazy[node];
  63. 		if(start!=end)
  64. 		{
  65. 			lazy[1+ 2*node]+=lazy[node];
  66. 			lazy[2+ 2*node]+=lazy[node];
  67. 		}
  68. 		lazy[node]=0;
  69. 	}
  70. 	*/
  71. 	if(l>end || start>r)
  72. 	 return;
  73.  
  74. 	if(start==end)
  75. 	{
  76. 		a[start]++;
  77. 		if(a[start]%3==0)
  78. 		 tree[node]=1;
  79. 		else tree[node]=0;
  80.  
  81. 		return;
  82. 	}
  83.  
  84. 	int mid= (start+end)/2;
  85.  
  86. 	 update(1+ 2*node, start, mid, l,r);
  87. 	 update(2+ 2*node, mid+1, end, l,r);
  88.      tree[node] = tree[1+ 2*node] + tree[2+ 2*node];
  89.  
  90. }
  91.  
  92. int main() {
  93. 	// your code goes here
  94. 	int n,f,x,y,i,q;
  95. 	//cin>>n>>q;
  96. 	S(n); S(q);
  97. 	build_tree(0,a,0,n-1);
  98. 	/*
  99. 	cout<<"The tree build is \n";
  100.  
  101. 	for(i=0;i<13;i++)
  102. 	 cout<<" i- "<<i<<": "<<tree[i]<<" \n";
  103.  
  104. 	*/
  105.  
  106. 	while(q--)
  107. 	{
  108. 		//cin>>f>>x>>y;
  109. 		S(f); S(x); S(y);
  110. 		if(f==1)
  111. 		cout<<get_mul(0,0,n-1,x,y)<<endl;
  112. 		else
  113. 		{
  114. 			update(0,0,n-1,x,y);
  115. 			/*cout<<"the tree is \n";
  116. 			for(i=0;i<13;i++)
  117. 			 cout<<tree[i]<<" ";
  118.  
  119. 			 cout<<endl;*/
  120. 		}
  121. 	}
  122.  
  123. 	return 0;
  124. }
Success #stdin #stdout 0s 5692KB
comments (?)
stdin
copy 
7 5
1 0 6
0 0 1
0 0 1
0 0 1
1 0 6
stdout
copy 
7
7
https://ideone.com/zIcmub
language:
C++ (gcc 8.3)
created:
9 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!