Dang_Quan_10_Tin

xquery

Sep 27th, 2021
923
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "xquery"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <cassert>
  8.  
  9. using namespace std;
  10.  
  11. using ll = long long;
  12. using ld = long double;
  13.  
  14. constexpr int N = 1e5 + 5;
  15.  
  16. struct node
  17. {
  18.     int cnt, v;
  19.     node *child[2];
  20.     node()
  21.     {
  22.         child[0] = child[1] = NULL;
  23.         cnt = v = 0;
  24.     }
  25. };
  26.  
  27. int q, t[N], x[N];
  28. int XOR;
  29.  
  30. void Read()
  31. {
  32.     cin >> q;
  33.     for (int i = 1; i <= q; ++i)
  34.         cin >> t[i] >> x[i];
  35. }
  36.  
  37. void Sub_1()
  38. {
  39.     vector<int> ans;
  40.  
  41.     for (int i = 1; i <= q; ++i)
  42.     {
  43.         if (t[i] == 0)
  44.             ans.emplace_back(x[i]);
  45.         else if (t[i] == 1)
  46.         {
  47.             for (int j = 0; j < (int)ans.size(); ++j)
  48.                 if (ans[j] == x[i])
  49.                 {
  50.                     ans[j] = ans.back();
  51.                     ans.pop_back();
  52.                     break;
  53.                 }
  54.         }
  55.         else if (t[i] == 2)
  56.         {
  57.             for (auto &j : ans)
  58.                 j ^= x[i];
  59.         }
  60.         else
  61.         {
  62.             ll sum(0);
  63.             for (int j = 0; j < x[i]; ++j)
  64.                 sum += ans[j];
  65.             cout << sum << "\n";
  66.         }
  67.         sort(ans.begin(), ans.end());
  68.     }
  69. }
  70.  
  71. #define bit(i, x) (((x) >> (i)) & 1)
  72.  
  73. struct Trie
  74. {
  75.     node root;
  76.     void Add(int x, int v)
  77.     {
  78.         node *a = &root;
  79.         int id(16);
  80.         while (1)
  81.         {
  82.             if (id == -1)
  83.             {
  84.                 ++(a->cnt);
  85.                 a->v += v;
  86.                 return;
  87.             }
  88.  
  89.             if (!(a->child[bit(id, x)]))
  90.                 a->child[bit(id, x)] = new node;
  91.  
  92.             ++(a->cnt);
  93.             a->v += v;
  94.             a = a->child[bit(id, x)];
  95.             --id;
  96.         }
  97.     }
  98.  
  99.     bool Erase(node *a, int x, int id, int v)
  100.     {
  101.         if (id == -1)
  102.         {
  103.             if (a->cnt > 0)
  104.             {
  105.                 --(a->cnt);
  106.                 a->v -= v;
  107.                 return true;
  108.             }
  109.             return false;
  110.         }
  111.  
  112.         if (!(a->child[bit(id, x)]))
  113.             return false;
  114.         if (!Erase(a->child[bit(id, x)], x, id - 1, v))
  115.             return false;
  116.  
  117.         --(a->cnt);
  118.         a->v -= v;
  119.  
  120.         return true;
  121.     }
  122.  
  123.     void Erase(int x, int v)
  124.     {
  125.         Erase(&root, x, 16, v);
  126.     }
  127.  
  128.     int Get(int k)
  129.     {
  130.         node *a = &root;
  131.         int id(16);
  132.         int ans(0);
  133.  
  134.         bool ok = k == 47;
  135.  
  136.         while (1)
  137.         {
  138.             if (id == -1)
  139.             {
  140.                 ans += min(k, a->v);
  141.                 break;
  142.             }
  143.             int cof[] = {0, 1};
  144.  
  145.             if (bit(id, XOR))
  146.                 swap(cof[0], cof[1]);
  147.  
  148.             if (a->child[cof[0]] && a->child[cof[0]]->cnt >= k)
  149.             {
  150.                 a = a->child[cof[0]];
  151.             }
  152.             else
  153.             {
  154.                 if (a->child[cof[0]])
  155.                 {
  156.                     ans += a->child[cof[0]]->v;
  157.                     k -= a->child[cof[0]]->cnt;
  158.                 }
  159.                 //assert(a->child[cof[1]] != NULL);
  160.                 a = a->child[cof[1]];
  161.             }
  162.  
  163.             --id;
  164.         }
  165.  
  166.         return ans;
  167.     }
  168.  
  169. } f[20];
  170.  
  171. void Add(int x)
  172. {
  173.     for (int i = 0; i < 17; ++i)
  174.         f[i].Add(x, bit(i, x));
  175. }
  176.  
  177. void Erase(int x)
  178. {
  179.     for (int i = 0; i < 17; ++i)
  180.         f[i].Erase(x, bit(i, x));
  181. }
  182.  
  183. ll Get(int k)
  184. {
  185.     if (k == 0)
  186.         return 0;
  187.     ll ans(0);
  188.     for (int i = 0; i < 17; ++i)
  189.     {
  190.         int v = f[i].Get(k);
  191.         ans += (bit(i, XOR) ? k - v : v) * (1 << i);
  192.     }
  193.  
  194.     return ans;
  195. }
  196.  
  197. void Sub_2()
  198. {
  199.     XOR = 0;
  200.     for (int i = 1; i <= q; ++i)
  201.     {
  202.         if (t[i] == 0)
  203.             Add(x[i] ^ XOR);
  204.         else if (t[i] == 1)
  205.             Erase(x[i] ^ XOR);
  206.         else if (t[i] == 2)
  207.             XOR ^= x[i];
  208.         else
  209.             cout << Get(x[i]) << "\n";
  210.     }
  211. }
  212.  
  213. int32_t main()
  214. {
  215.     ios::sync_with_stdio(0);
  216.     cin.tie(0);
  217.     cout.tie(0);
  218.     if (fopen(task ".INP", "r"))
  219.     {
  220.         freopen(task ".INP", "r", stdin);
  221.         freopen(task ".OUT", "w", stdout);
  222.     }
  223.     Read();
  224.     if (q <= 1000)
  225.         Sub_1();
  226.     else
  227.         Sub_2();
  228. }
  229.  
RAW Paste Data