Advertisement
ivnikkk

Untitled

Jan 23rd, 2022
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None | 0 0
  1. #pragma GCC optimize("03")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. using namespace chrono;
  6. #define all(a) a.begin(), a.end()
  7. #define allr(a) a.rbegin(), a.rend()
  8. #define endl "\n"
  9. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. constexpr int N = 65;
  14. const int MAXN = 5e5 + 10;
  15. bitset<N> tree[4 * MAXN];
  16. bitset<N> mod[4 * MAXN];
  17. int a[MAXN];
  18. void build(ll v, ll tl, ll tr) {
  19.     if (tl == tr) {
  20.         tree[v] = a[tl];
  21.         return;
  22.     }
  23.     ll mid = (tl + tr) >> 1;
  24.     build(v << 1, tl, mid);
  25.     build((v << 1) | 1, mid + 1, tr);
  26.     tree[v] = tree[v << 1] ^ tree[(v << 1) | 1];
  27. }
  28. void push(ll v) {
  29.     tree[v] = tree[v] ^ mod[v];
  30.     if ((v << 1) | 1 > 4 * MAXN) {
  31.         mod[v] = 0;
  32.         return;
  33.     }
  34.         mod[v << 1] = mod[v << 1] ^ mod[v];
  35.         mod[(v << 1) | 1] = mod[(v << 1) | 1] ^ mod[v];
  36.         mod[v] = 0;
  37. }
  38. void update(ll v, ll tl, ll tr, ll l, ll r, ll x) {
  39.     push(v);
  40.     if (tr<l || tl>r) {
  41.         return;
  42.     }
  43.     if (tl >= l && tr <= r) {
  44.             bitset<N> sub = x;
  45.             mod[v] = mod[v] ^ sub ;
  46.         push(v);
  47.     }
  48.     ll mid = (tl + tr) / 2;
  49.     update(v << 1, tl, mid, l, r, x);
  50.     update((v << 1) | 1, mid + 1, tr, l, r, x);
  51.     tree[v] = tree[v << 1] ^ tree[(v << 1) | 1];
  52. }
  53. bitset<N> get_xor(ll v, ll tl ,ll tr, ll l, ll r) {
  54.     push(v);
  55.     if (tr<l || tl>r) {
  56.         return 0;
  57.     }
  58.     if (tl >= l && tr <= r) {
  59.         return tree[v];
  60.     }
  61.     ll mid = (tl + tr) / 2;
  62.     return get_xor(v * 2, tl, mid, l, r) ^ get_xor(v * 2 + 1, mid + 1, tr, l, r);
  63. }
  64. signed main() {
  65. #ifdef _DEBUG
  66.     freopen("input.txt", "r", stdin);
  67.     freopen("output.txt", "w", stdout);
  68. #endif
  69.     ios_base::sync_with_stdio(false);
  70.     cin.tie(nullptr);
  71.     cout.tie(nullptr);
  72.     srand(time(NULL));
  73.     ll n, m;
  74.     cin >> n >> m;
  75.     for (ll i = 0; i < n; i++) {
  76.         cin >> a[i];
  77.     }
  78.     ll m;
  79.     cin >> m;
  80.     for (ll i = 0; i < m; i++) {
  81.         string s;
  82.         cin >> s;
  83.         if (s == "get") {
  84.             string xr;
  85.             cin >> xr;
  86.             if (xr == "xor") {
  87.                 ll l, r, x;
  88.                 cin >> l >> r;
  89.                 l--, r--;
  90.                 bitset<N>ans = get_xor(1, 0, n - 1, l, r);
  91.  
  92.             }
  93.         }
  94.         else if (s == "upd") {
  95.             string xr;
  96.             cin >> xr;
  97.             if (xr == "xor") {
  98.                 ll l, r, x;
  99.                 cin >> l >> r >> x;
  100.                 l--, r--;
  101.                 update(1, 0, n - 1, l, r,x);
  102.  
  103.             }
  104.         }
  105.     }
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement