fork download
copy 
  1. // just segt.. i want this one to TLE 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. /*
  5. 4 7
  6. 1 0 3
  7. 0 1 2
  8. 1 0 1
  9. 1 0 0
  10. 0 0 3
  11. 1 0 3 
  12. 1 3 3
  13. */
  14. int st[500005];
  15. //~ void init(int lo,int hi,int idx){
  16. 	//~ for(int i=0;i<100005;i++){
  17. 		//~ st[i].coin=false;
  18. 		//~ st[i].count=0;
  19. 		//~ }
  20. 	//~ return;
  21. 	//~ if(lo==hi){
  22. 		//~ st[idx].coin=false;//means its tails...
  23. 		//~ st[idx].count=0;
  24. 		//~ return ;
  25. 		//~ }
  26. 	//~ init(lo,(lo+hi)/2,2*idx);
  27. 	//~ init(((lo+hi)/2) +1,hi,2*idx+1);
  28. 	//~ st[idx].count=(st[2*idx].count + st[2*idx+1].count);
  29. 	//~ }
  30.  
  31. void flip(int lo,int hi,int s,int e,int idx){
  32. 	int pp;
  33. 	if(s>hi || e<lo)return ;
  34. 	if(lo>=s && hi<=e)st[idx]=(hi-lo+1)-st[idx];//total children-all set nodes
  35. 	if(lo==hi)return;
  36. 	//cout<<"hi "<<lo<<" "<<idx;cin>>pp;
  37. 	flip(lo,(lo+hi)/2, s,e,2*idx);
  38. 	flip(((lo+hi)/2) +1,hi, s,e,2*idx+1);
  39. 	st[idx]=st[2*idx] + st[2*idx+1];
  40. 	}
  41. int query(int lo,int hi,int s,int e,int idx){
  42. 	if(s>hi || e<lo)return 0;//nasty..
  43. 	int pp;
  44. 	if(lo>=s && hi<=e)return st[idx];
  45. 	if(lo==hi)return st[lo];
  46. 	//cout<<"hi "<<lo<<" "<<idx;cin>>pp;
  47. 	int x=query(lo,(lo+hi)/2,s,e,2*idx);
  48. 	int y=query((lo+hi)/2+1,hi,s,e,2*idx+1);
  49. 	return x+y;
  50. 	}
  51. int main(){
  52. 	int n,q,i;
  53. 	scanf("%d%d", &n,&q);
  54. 	for(i=0;i<q;i++){
  55. 		int tp,a,b;
  56. 		scanf("%d%d%d",&tp,&a,&b);
  57. 		a+=1;b+=1;
  58. 		if(tp==0)flip(1,n,a,b,1);
  59. 		else printf("%d\n",query(1,n,a,b,1));
  60. 		}
  61. 	return 0;
  62. 	}
  63.  
Success #stdin #stdout 0s 5412KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3
stdout
copy 
0
1
0
2
1
https://ideone.com/JFFws1
language:
C++ (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!