aayyk

vsesib e 100 (rip ya debil)

Feb 23rd, 2021
483
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2.  
  3. #ifdef LOCAL
  4. #include "debug.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define debug(x...)
  10. #endif
  11.  
  12. using namespace std;
  13.  
  14. //#define int ll
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. typedef pair <int, int> pii;
  19. #define sz(x) int((x).size())
  20.  
  21. template <typename T>
  22. using ordered_set = __gnu_pbds::tree <T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  23.  
  24. #ifdef ONLINE_JUDGE
  25. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  26. #else
  27. mt19937 rng(1000 - 7);
  28. #endif
  29.  
  30. const int N = 1e5 + 10;
  31. const ll MOD = 1e9 + 7;
  32. //const ll MOD = 998244353;
  33. const ld eps = 5e-8;
  34. const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  35.  
  36. const int C = 30;
  37.  
  38. signed main() {
  39. #ifdef LOCAL
  40.     freopen("input.txt", "r", stdin);
  41.     freopen("output.txt", "w", stdout);
  42. #endif
  43.     cout << fixed << setprecision(9);
  44.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  45.  
  46.     int q;
  47.     cin >> q;
  48.  
  49.     vector <int> a;
  50.     vector <tuple <int, int, int, int>> qq;
  51.  
  52.     while (q--) {
  53.         char type;
  54.         cin >> type;
  55.  
  56.         if (type == '+') {
  57.             int x;
  58.             cin >> x;
  59.  
  60.             a.push_back(x);
  61.         }
  62.         else {
  63.             int l, r, x, k;
  64.             cin >> l >> r >> x >> k;
  65.  
  66.             l--, r--;
  67.  
  68.             qq.push_back({ l, r, x, k });
  69.         }
  70.     }
  71.  
  72.     int n = a.size();
  73.  
  74.     //unordered_map <pair<int, int>, vector <int>, Hasher> suff;
  75.     //unordered_map <pair<int, int>, vector <vector <int>>, Hasher> sum;
  76.    
  77.     map <pair<int, int>, vector <int>> suff;
  78.     map <pair<int, int>, vector <vector <int>>> sum;
  79.  
  80.     for (int i = 0; i < n; i++) {
  81.         int x = a[i];
  82.         suff[make_pair(x, -1)].push_back(i);
  83.  
  84.         for (int j = 0; j < C; j++) {
  85.             x = x & (~0 - (1 << j));
  86.             suff[make_pair(x, j)].push_back(i);
  87.         }
  88.     }
  89.  
  90.     for (auto& [k, v] : suff) {
  91.         sum[k] = vector <vector <int>> (v.size(), vector <int> (C));
  92.         vector <vector <int>>& ref = sum[k];
  93.  
  94.         int x = a[v.front()];
  95.         for (int j = 0; j < C; j++) {
  96.             ref.front()[j] = x >> j & 1;
  97.         }
  98.  
  99.         for (int i = 1; i < sz(v); i++) {
  100.             x = a[v[i]];
  101.             for (int j = 0; j < C; j++) {
  102.                 ref[i][j] = ref[i - 1][j] + (x >> j & 1);
  103.             }
  104.         }
  105.     }
  106.  
  107.     auto get = [&] (pair <int, int> mask, int i, int j, int x) -> ll {
  108.         if (j < 0) return 0LL;
  109.  
  110.         vector <vector <int>>& s = sum[mask];
  111.  
  112.         ll res = 0;
  113.         for (int b = 0; b < C; b++) {
  114.             if (x >> b & 1) {
  115.                 res += (1LL << b) * (j + 1 - s[j][b]);
  116.             }
  117.             else {
  118.                 res += (1LL << b) * s[j][b];
  119.             }
  120.         }
  121.  
  122.         if (i >= 0) {
  123.             for (int b = 0; b < C; b++) {
  124.                 if (x >> b & 1) {
  125.                     res -= (1LL << b) * (i + 1 - s[i][b]);
  126.                 }
  127.                 else {
  128.                     res -= (1LL << b) * s[i][b];
  129.                 }
  130.             }
  131.         }
  132.  
  133.         return res;
  134.     };
  135.  
  136.     auto ind = [&] (pair <int, int> mask, int l, int r) {
  137.         vector <int>& ref = suff[mask];
  138.         int i = lower_bound(ref.begin(), ref.end(), l) - ref.begin() - 1;
  139.         int j = upper_bound(ref.begin(), ref.end(), r) - ref.begin() - 1;
  140.  
  141.         return make_pair(i, j);
  142.     };
  143.  
  144.     for (auto [l, r, x, k] : qq) {
  145.         int mask = 0;
  146.         ll ans = 0;
  147.  
  148.         for (int i = C - 1; i >= 0; i--) {
  149.             if (x >> i & 1) {
  150.                 auto [u, v] = ind({ mask, i - 1 }, l, r);
  151.                 int cnt = v - u;
  152.  
  153.                 if (k > cnt) {
  154.                     ans += get({ mask, i - 1 }, u, v, x);
  155.                     mask |= (1 << i);
  156.                     k -= cnt;
  157.                 }
  158.             }
  159.             else {
  160.                 auto [u, v] = ind({ mask | (1 << i), i - 1 }, l, r);
  161.                 int cnt = v - u;
  162.  
  163.                 if (k <= cnt) {
  164.                     mask |= (1 << i);
  165.                 }
  166.                 else {
  167.                     ans += get({ mask | (1 << i), i - 1 }, u, v, x);
  168.                     k -= cnt;
  169.                 }
  170.             }
  171.         }
  172.  
  173.         ans += (mask ^ x) * k;
  174.  
  175.         cout << ans << "\n";
  176.     }
  177.  
  178.     return 0;
  179. }
  180.  
RAW Paste Data