Dang_Quan_10_Tin

THT Sơ Khảo C (2021) XORLRC

Oct 16th, 2021
732
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Meet in the middle approach */
  2.  
  3. #define task "XORLRC"
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <cstring>
  8. #include <vector>
  9. #include <algorithm>
  10.  
  11. using namespace std;
  12.  
  13. using ll = long long;
  14. using ld = long double;
  15.  
  16. constexpr int N = 1e5 + 5;
  17. constexpr ll Inf = 1e17;
  18.  
  19. struct SegmentTree
  20. {
  21.     int n, cnt[N * 4];
  22.     ll st[N * 4];
  23.  
  24.     void Build(int id, int l, int r, const vector<pair<int, ll>> &a)
  25.     {
  26.         if (l == r)
  27.         {
  28.             st[id] = a[l - 1].second;
  29.             cnt[id] = 1;
  30.             return;
  31.         }
  32.         Build(id << 1, l, (l + r) / 2, a);
  33.         Build(id << 1 | 1, (l + r) / 2 + 1, r, a);
  34.  
  35.         if (st[id << 1] > st[id << 1 | 1])
  36.         {
  37.             st[id] = st[id << 1];
  38.             cnt[id] = cnt[id << 1];
  39.         }
  40.         else if (st[id << 1 | 1] > st[id << 1])
  41.         {
  42.             st[id] = st[id << 1 | 1];
  43.             cnt[id] = cnt[id << 1 | 1];
  44.         }
  45.         else
  46.         {
  47.             st[id] = st[id << 1 | 1];
  48.             cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
  49.         }
  50.     }
  51.  
  52.     void Build(const vector<pair<int, ll>> &a)
  53.     {
  54.         Build(1, 1, n, a);
  55.     }
  56.  
  57.     pair<ll, int> Get(int id, int l, int r, const int &a, const int &b)
  58.     {
  59.         if (l > b || r < a)
  60.             return make_pair(-Inf, 0);
  61.         if (l >= a && r <= b)
  62.             return make_pair(st[id], cnt[id]);
  63.         pair<ll, int> u = Get(id << 1, l, (l + r) / 2, a, b),
  64.                       v = Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b);
  65.  
  66.         if (u.first > v.first)
  67.             return u;
  68.         if (v.first > u.first)
  69.             return v;
  70.         return make_pair(u.first, u.second + v.second);
  71.     }
  72.  
  73.     pair<ll, int> Get(int l, int r)
  74.     {
  75.         ++l;
  76.         ++r;
  77.         return Get(1, 1, n, l, r);
  78.     }
  79. } seg;
  80.  
  81. int n, a[N], l, r, k, g[32][2][2], cnt[32], res[N];
  82. ll dp[32][2][2];
  83.  
  84. #define bit(i, x) (((x) >> (i)) & 1)
  85.  
  86. void Read()
  87. {
  88.     cin >> n >> l >> r >> k;
  89.     for (int i = 1; i <= n; ++i)
  90.     {
  91.         cin >> a[i];
  92.         for (int j = 0; j < 30; ++j)
  93.             if (bit(j, a[i]))
  94.                 ++cnt[j];
  95.     }
  96. }
  97.  
  98. void Sub_4()
  99. {
  100.     vector<pair<int, ll>> a;
  101.  
  102.     for (int i = 0; i < (1 << 15); ++i)
  103.     {
  104.         ll tmp(0);
  105.  
  106.         for (int j = 15; j < 30; ++j)
  107.             if (bit(j - 15, i))
  108.                 tmp += (1ll << j) * (n - cnt[j]);
  109.             else
  110.                 tmp += (1ll << j) * cnt[j];
  111.  
  112.         a.emplace_back(i << 15, tmp);
  113.     }
  114.  
  115.     sort(a.begin(), a.end(), [&](const pair<int, ll> &a, const pair<int, ll> &b)
  116.          { return a.first % k < b.first % k || (a.first % k == b.first % k && a.first < b.first); });
  117.  
  118.     seg.n = a.size();
  119.     seg.Build(a);
  120.  
  121.     ll ans(0);
  122.     int L = l, R = r, nums(0);
  123.  
  124.     for (int i = 0; i < (1 << 15); ++i)
  125.     {
  126.         ll tmp(0);
  127.  
  128.         for (int j = 0; j < 15; ++j)
  129.             if (bit(j, i))
  130.                 tmp += (1ll << j) * (n - cnt[j]);
  131.             else
  132.                 tmp += (1ll << j) * cnt[j];
  133.  
  134.         int l = 0, m, h = (int)a.size() - 1;
  135.         int need = (k - i % k) % k;
  136.         while (l <= h)
  137.         {
  138.             m = (l + h) / 2;
  139.             if (a[m].first % k < need)
  140.                 l = m + 1;
  141.             else
  142.                 h = m - 1;
  143.         }
  144.  
  145.         int pl = l;
  146.  
  147.         h = (int)a.size() - 1;
  148.  
  149.         while (l <= h)
  150.         {
  151.             m = (l + h) / 2;
  152.             if (a[m].first % k <= need)
  153.                 l = m + 1;
  154.             else
  155.                 h = m - 1;
  156.         }
  157.  
  158.         int pr = h;
  159.  
  160.         l = pl, h = pr;
  161.  
  162.         while (l <= h)
  163.         {
  164.             m = (l + h) / 2;
  165.             if (a[m].first < L - i)
  166.                 l = m + 1;
  167.             else
  168.                 h = m - 1;
  169.         }
  170.  
  171.         int ppl = l;
  172.  
  173.         h = pr;
  174.  
  175.         while (l <= h)
  176.         {
  177.             m = (l + h) / 2;
  178.             if (a[m].first <= R - i)
  179.                 l = m + 1;
  180.             else
  181.                 h = m - 1;
  182.         }
  183.  
  184.         int ppr = h;
  185.  
  186.         if (ppl <= ppr)
  187.         {
  188.             pair<ll, int> v = seg.Get(ppl, ppr);
  189.             if (ans < tmp + v.first)
  190.             {
  191.                 ans = tmp + v.first;
  192.                 nums = v.second;
  193.             }
  194.             else if (ans == tmp + v.first)
  195.                 nums += v.second;
  196.         }
  197.     }
  198.  
  199.     cout << ans << "\n"
  200.          << nums;
  201. }
  202.  
  203. int32_t main()
  204. {
  205.     ios::sync_with_stdio(0);
  206.     cin.tie(0);
  207.     cout.tie(0);
  208.     if (fopen(task ".INP", "r"))
  209.     {
  210.         freopen(task ".INP", "r", stdin);
  211.         freopen(task ".OUT", "w", stdout);
  212.     }
  213.     Read();
  214.     Sub_4();
  215. }
RAW Paste Data