THT Sơ Khảo C (2021) XORLRC

/* Meet in the middle approach */

#define task "XORLRC"

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;

struct SegmentTree
{
    int n, cnt[N * 4];
    ll st[N * 4];

    void Build(int id, int l, int r, const vector<pair<int, ll>> &a)
    {
        if (l == r)
        {
            st[id] = a[l - 1].second;
            cnt[id] = 1;
            return;
        }
        Build(id << 1, l, (l + r) / 2, a);
        Build(id << 1 | 1, (l + r) / 2 + 1, r, a);

        if (st[id << 1] > st[id << 1 | 1])
        {
            st[id] = st[id << 1];
            cnt[id] = cnt[id << 1];
        }
        else if (st[id << 1 | 1] > st[id << 1])
        {
            st[id] = st[id << 1 | 1];
            cnt[id] = cnt[id << 1 | 1];
        }
        else
        {
            st[id] = st[id << 1 | 1];
            cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
        }
    }

    void Build(const vector<pair<int, ll>> &a)
    {
        Build(1, 1, n, a);
    }

    pair<ll, int> Get(int id, int l, int r, const int &a, const int &b)
    {
        if (l > b || r < a)
            return make_pair(-Inf, 0);
        if (l >= a && r <= b)
            return make_pair(st[id], cnt[id]);
        pair<ll, int> u = Get(id << 1, l, (l + r) / 2, a, b),
                      v = Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b);

        if (u.first > v.first)
            return u;
        if (v.first > u.first)
            return v;
        return make_pair(u.first, u.second + v.second);
    }

    pair<ll, int> Get(int l, int r)
    {
        ++l;
        ++r;
        return Get(1, 1, n, l, r);
    }
} seg;

int n, a[N], l, r, k, g[32][2][2], cnt[32], res[N];
ll dp[32][2][2];

#define bit(i, x) (((x) >> (i)) & 1)

void Read()
{
    cin >> n >> l >> r >> k;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        for (int j = 0; j < 30; ++j)
            if (bit(j, a[i]))
                ++cnt[j];
    }
}

void Sub_4()
{
    vector<pair<int, ll>> a;

    for (int i = 0; i < (1 << 15); ++i)
    {
        ll tmp(0);

        for (int j = 15; j < 30; ++j)
            if (bit(j - 15, i))
                tmp += (1ll << j) * (n - cnt[j]);
            else
                tmp += (1ll << j) * cnt[j];

        a.emplace_back(i << 15, tmp);
    }

    sort(a.begin(), a.end(), [&](const pair<int, ll> &a, const pair<int, ll> &b)
         { return a.first % k < b.first % k || (a.first % k == b.first % k && a.first < b.first); });

    seg.n = a.size();
    seg.Build(a);

    ll ans(0);
    int L = l, R = r, nums(0);

    for (int i = 0; i < (1 << 15); ++i)
    {
        ll tmp(0);

        for (int j = 0; j < 15; ++j)
            if (bit(j, i))
                tmp += (1ll << j) * (n - cnt[j]);
            else
                tmp += (1ll << j) * cnt[j];

        int l = 0, m, h = (int)a.size() - 1;
        int need = (k - i % k) % k;
        while (l <= h)
        {
            m = (l + h) / 2;
            if (a[m].first % k < need)
                l = m + 1;
            else
                h = m - 1;
        }

        int pl = l;

        h = (int)a.size() - 1;

        while (l <= h)
        {
            m = (l + h) / 2;
            if (a[m].first % k <= need)
                l = m + 1;
            else
                h = m - 1;
        }

        int pr = h;

        l = pl, h = pr;

        while (l <= h)
        {
            m = (l + h) / 2;
            if (a[m].first < L - i)
                l = m + 1;
            else
                h = m - 1;
        }

        int ppl = l;

        h = pr;

        while (l <= h)
        {
            m = (l + h) / 2;
            if (a[m].first <= R - i)
                l = m + 1;
            else
                h = m - 1;
        }

        int ppr = h;

        if (ppl <= ppr)
        {
            pair<ll, int> v = seg.Get(ppl, ppr);
            if (ans < tmp + v.first)
            {
                ans = tmp + v.first;
                nums = v.second;
            }
            else if (ans == tmp + v.first)
                nums += v.second;
        }
    }

    cout << ans << "\n"
         << nums;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Sub_4();
}