fork download 
  1. /*screw_1011*/
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MP make_pair
  5. #define PB push_back
  6. #define MOD 1000000007
  7. #define ll long long int
  8. int lazy[200005];
  9. struct node
  10. {
  11. 	int a1; ///a1 = lights are in on
  12. 	int b1; ///b1 = lights are in off 
  13. }st[200005];
  14. // qs = querry starting 
  15. // qe = querry ending
  16. // ss = segment starting
  17. // se = segment ending
  18. // index = level of the seg tree
  19. int get(int ss,int se,int qs,int qe,int index)
  20. {
  21. 	if(qs>se || qe<ss)
  22. 	return 0;
  23. 	if(lazy[index]!=0)
  24. 	{
  25. 		int tmp;
  26. 		tmp = st[index].a1;
  27. 		st[index].a1 = st[index].b1;
  28. 		st[index].b1 = tmp;
  29. 		if(ss!=se)
  30. 		{
  31. 			if(lazy[2*index+1]==0)
  32. 			lazy[2*index+1] = 1;
  33. 			else
  34. 			lazy[2*index+1] = 0;
  35. 			if(lazy[2*index+2] == 0)
  36. 			lazy[2*index+2] = 1;
  37. 			else
  38. 			lazy[2*index+2] = 0;
  39. 		}
  40. 		lazy[index] = 0;
  41. 	}
  42. 	if(qs<=ss & qe>=se)
  43. 	return st[index].a1;
  44. 	int mid = ss + (se-ss)/2;
  45. 	return get(ss,mid,qs,qe,2*index+1) + get(mid+1,se,qs,qe,2*index+2);
  46. }
  47. void update(int ss,int se,int qs,int qe,int index)
  48. {
  49. 	//node needs to be updated or not
  50. 	if(lazy[index]!=0)
  51. 	{
  52. 		//switch karna hai iss index par
  53. 		int tmp;
  54. 		tmp = st[index].a1;
  55. 		st[index].a1 = st[index].b1;
  56. 		st[index].b1 = tmp;
  57. 		//if not a leaf node , mark the childs as lazy
  58. 		if(ss!=se)
  59. 		{
  60. 			if(lazy[2*index+1]==0)
  61. 			lazy[2*index+1] = 1;
  62. 			else
  63. 			lazy[2*index+1] = 0;
  64. 				if(lazy[2*index+2]==0)
  65. 				lazy[2*index+2] = 1;
  66. 				else
  67. 				lazy[2*index+2] = 0;
  68. 		}
  69. 		lazy[index] = 0;
  70. 	}
  71. 	if(qs>se || qe<ss)
  72. 	return ;
  73. 	if(qs<=ss && qe>=se)
  74. 	{
  75. 		int tmp1;
  76. 		tmp1 = st[index].a1;
  77. 		st[index].a1 = st[index].b1;
  78. 		st[index].b1 = tmp1;
  79. 		if(ss!=se)
  80. 		{
  81. 			if(lazy[2*index+1]==1)
  82. 			lazy[2*index+1] = 0;
  83. 			else
  84. 			lazy[2*index+1] = 1;
  85. 				if(lazy[2*index+2]==1)
  86. 				lazy[2*index+2] = 0;
  87. 				else
  88. 				lazy[2*index+2] = 1;
  89. 		}
  90. 		return ;
  91. 	}
  92. 	int mid = ss + (se-ss)/2;
  93. 	update(ss,mid,qs,qe,2*index+1);
  94. 	update(mid+1,se,qs,qe,2*index+2);
  95. 	st[index].a1 = st[2*index+1].a1 + st[2*index+2].a1;
  96. 	st[index].b1 = st[2*index+1].b1 + st[2*index+2].b1;
  97. }
  98. void coseg(int ss,int se,int index)
  99. {
  100. 	if(ss==se)
  101. 	{
  102. 		st[index].a1 = 0;
  103. 		st[index].b1 = 1;
  104. 		return ;
  105. 	}
  106. 	int mid = ss + (se-ss)/2;
  107. 	coseg(ss,mid,2*index+1);
  108. 	coseg(mid+1,se,2*index+2);
  109. 	st[index].a1 = st[2*index+1].a1 + st[2*index+2].a1;
  110. 	st[index].b1 = st[2*index+1].b1 + st[2*index+2].b1; 
  111. }
  112. int main()
  113. {
  114. 	int t,n,m,p,q,x,ans;
  115. 	scanf("%d%d",&n,&m);
  116.  
  117. 	coseg(0,n-1,0);
  118. 	while(m--)
  119. 	{
  120. 		scanf("%d",&x);
  121. 		if(x==0)
  122. 		{
  123. 			scanf("%d%d",&p,&q);
  124. 			update(0,n-1,p-1,q-1,0);
  125. 		}
  126. 		else
  127. 		{
  128. 			scanf("%d%d",&p,&q);
  129. 			ans = get(0,n-1,p-1,q-1,0);
  130. 			printf("%d\n",ans);
  131. 		}
  132. 	}
  133. 	return 0;
  134. }
  135.  
Success #stdin #stdout 0s 5076KB
comments (?)
stdin 
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
stdout 
1
2
https://ideone.com/VvsG7c
language:
C++ 4.3.2 (gcc-4.3.2)
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!