提出 #69672102

---

ソースコード 拡げる

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = std::forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = std::forward<U>(y), true); }

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

using namespace std;

using ll = long long;

template <typename T, int MAX_LOG> struct BinaryTrie {
    struct Node {
        std::array<int, 2> nxt;
        int count;
        Node() : nxt{-1, -1}, count(0) {}
    };

    std::vector<Node> nodes;

    inline int& next(int i, int j) { return nodes[i].nxt[j]; }

    BinaryTrie() { nodes.emplace_back(); }

    void insert(const T& x) {
        int cur = 0;
        for (int i = MAX_LOG - 1; i >= 0; i--) {
            int f = x >> i & 1;
            int nxt = next(cur, f);
            if (nxt == -1) {
                nxt = nodes.size();
                next(cur, f) = nxt;
                nodes.emplace_back();
            }
            nodes[cur].count++;
            cur = nxt;
        }
        nodes[cur].count++;
    }
};

const int MAX_LOG = 30;

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    BinaryTrie<int, MAX_LOG> bt;
    for (int i = 0; i < N; i++) {
        bt.insert(A[i]);
    }

    auto g = [&](int k, int x) -> int {  // x 未満で k bit 目が 1 となる整数の個数
        int tmp = x;
        int cycle = 1 << (k + 1);
        int res = x / cycle * (1 << k);
        x %= cycle;
        res += min(1 << k, x);
        return tmp - res;
    };
    auto f = [&](int k, int l, int r) -> int { return g(k, r) - g(k, l); };
    auto dfs = [&](auto self, int cur, int d, int l, int r) -> ll {
        if (r <= l or d == -1) {
            return 0;
        }
        ll res = 0;
        auto L = bt.next(cur, 0), R = bt.next(cur, 1);
        if (L != -1 and R != -1) {
            assert(l == 0);
            int cycle = 1 << (d + 1);
            int weight = r / cycle;
            r %= cycle;
            auto xl = self(self, L, d - 1, 0, 1 << d);
            auto xr = self(self, R, d - 1, 0, 1 << d);
            res += (xl + xr) * weight;
            if (r <= cycle / 2) {
                res += self(self, L, d - 1, 0, r);
            } else {
                res += xl;
                res += self(self, R, d - 1, 0, r - (1 << d));
            }
        } else if (L != -1) {
            res += f(d, l, r) * (1LL << d);
            res += self(self, L, d - 1, l, r);
        } else {
            assert(R != -1);
            res += ((r - l) - f(d, l, r)) * (1LL << d);
            res += self(self, R, d - 1, l, r);
        }
        return res;
    };
    ll ans = dfs(dfs, 0, MAX_LOG - 1, 0, M);

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    solve();
    return 0;
}

提出情報

ジャッジ結果