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
stdin
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
stdout
1
2