Advertisement
Vince14

/<> 12844 (lazy propagation xor)

Oct 28th, 2023
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | Source Code | 0 0
  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 = 500005;
  23.  
  24. int n, m;
  25. int arr[MAXN];
  26. int seg[MAXN * 4], lazy[MAXN * 4];
  27.  
  28. void prop(int x, int s, int e){
  29.     if(lazy[x] == 0) return;
  30.     if((e - s) % 2 == 0) seg[x] ^= lazy[x];
  31.     if(s == e){
  32.         lazy[x] = 0;
  33.     }
  34.     else{
  35.         lazy[x * 2] ^= lazy[x];
  36.         lazy[x * 2 + 1] ^= lazy[x];
  37.         lazy[x] = 0;
  38.     }
  39. }
  40.  
  41. void build(int x, int s, int e){
  42.     if(s == e){
  43.         seg[x] = arr[s];
  44.         return;
  45.     }
  46.     int mid = (s + e) / 2;
  47.     build(x * 2, s, mid);
  48.     build(x * 2 + 1, mid + 1, e);
  49.     seg[x] = seg[x * 2] ^ seg[x * 2 + 1];
  50. }
  51.  
  52. void update(int x, int s, int e, int a, int b, int k){
  53.     prop(x, s, e);
  54.     if(b < s || e < a) return;
  55.     if(a <= s && e <= b){
  56.         lazy[x] ^= k;
  57.         prop(x, s, e);
  58.         return;
  59.     }
  60.     int mid = (s + e) / 2;
  61.     update(x * 2, s, mid, a, b, k);
  62.     update(x * 2 + 1, mid + 1, e, a, b, k);
  63.     seg[x] = seg[x * 2] ^ seg[x * 2 + 1];
  64. }
  65.  
  66. int query(int x, int s, int e, int a, int b){
  67.     prop(x, s, e);
  68.     if(b < s || e < a) return 0;
  69.     if(a <= s and e <= b){
  70.         return seg[x];
  71.     }
  72.     int mid = (s + e) / 2;
  73.     return query(x * 2, s, mid, a, b) ^ query(x * 2 + 1, mid + 1, e, a, b);
  74. }
  75.  
  76. int main() {
  77.     FAST;
  78.     cin >> n;
  79.     for(int i = 1; i <= n; i++){
  80.         cin >> arr[i];
  81.     }
  82.     build(1, 1, n);
  83.     cin >> m;
  84.     for(int q, i, j, k, l = 0; l < m; l++){
  85.         cin >> q >> i >> j;
  86.         i++; j++;
  87.         if(q == 1){
  88.             cin >> k;
  89.             update(1, 1, n, i, j, k);
  90.         }
  91.         else{
  92.             cout << query(1, 1, n, i, j) << "\n";
  93.         }
  94.     }
  95. }
  96.  
  97.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement