Advertisement
Vince14

/<> 1395 (lazy propagation seg)

Sep 23rd, 2023
328
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<long long, long long>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 100005;
  23.  
  24. int N, M;
  25. int seg[MAXN * 4];
  26. bool lazy[MAXN * 4];
  27.  
  28. void prop(int x, int s, int e){
  29.     if(!lazy[x]) return;
  30.     seg[x] = (e + 1 - s) - seg[x];
  31.     if(s != e){
  32.         lazy[x * 2] = !lazy[x * 2];
  33.         lazy[x * 2 + 1] = !lazy[x * 2 + 1];
  34.     }
  35.     lazy[x] = false;
  36. }
  37.  
  38. void update(int x, int s, int e, int a, int b){
  39.     prop(x, s, e);
  40.     if(b < s or e < a) return;
  41.     if(a <= s and e <= b){
  42.         lazy[x] = !lazy[x];
  43.         prop(x, s, e);
  44.         return;
  45.     }
  46.     int mid = (s + e)/2;
  47.     update(x * 2, s, mid, a, b);
  48.     update(x * 2 + 1, mid + 1, e, a, b);
  49.     seg[x] = seg[x * 2] + seg[x * 2 + 1];
  50. }
  51.  
  52. int query(int x, int s, int e, int a, int b){
  53.     prop(x, s, e);
  54.     if(b < s or e < a) return 0;
  55.     if(a <= s and e <= b) return seg[x];
  56.     int mid = (s + e)/2;
  57.     int q1 = query(x * 2, s, mid, a, b);
  58.     int q2 = query(x * 2 + 1, mid + 1, e, a, b);
  59.     // cout << s << " to " << e << ": " << q1 << " " << q2 << "\n";
  60.     return q1 + q2;
  61. }
  62.  
  63. int main() {
  64.     FAST;
  65.     cin >> N >> M;
  66.     for(int a, b, c, i = 0; i < M; i++){
  67.         cin >> a >> b >> c;
  68.         if(a == 0){
  69.             if(b > c){
  70.                 swap(b, c);
  71.             }
  72.             update(1, 1, N, b, c);
  73.  
  74.         }
  75.         else{
  76.             if(b > c){
  77.                 swap(b, c);
  78.             }
  79.             // cout << "Start query " << b << " " << c << ":\n";
  80.             cout << query(1, 1, N, b, c) << "\n";
  81.         }
  82.     }
  83. }
  84.  
  85. /*
  86. 4 5
  87. 0 1 2
  88. 0 2 4
  89. 1 2 3
  90. 0 2 4
  91. 1 1 4
  92.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement