aayyk

Untitled

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