遭到东方明珠的攻击

将区间集合建成压缩二进制Trie，按最高不同位递归统计三元组，并用异或阈值下的邻居数一阶、二阶矩高效计算跨子树贡献。

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;

const ll MOD = 1000000007LL;
const ll INV2 = 500000004LL;
const ll INV6 = 166666668LL;
const int B = 30;

struct Node {
    int lc = 0, rc = 0, match = 0;
    unsigned int cnt = 0;
};

vector<Node> tr;
vector<int> dp1, dp2, dp3;
ull K;

inline ull sizeOf(int d) {
    return 1ULL << (B - d);
}

int newNode() {
    tr.push_back(Node());
    return (int)tr.size() - 1;
}

void insertInterval(int u, int d, ull L, ull R, ull ql, ull qr) {
    if (ql <= L && R <= qr) {
        tr[u].cnt = (unsigned int)sizeOf(d);
        tr[u].lc = tr[u].rc = 0;
        return;
    }

    ull mid = (L + R) >> 1;

    if (ql <= mid) {
        if (!tr[u].lc) tr[u].lc = newNode();
        insertInterval(tr[u].lc, d + 1, L, mid, ql, qr);
    }

    if (qr > mid) {
        if (!tr[u].rc) tr[u].rc = newNode();
        insertInterval(tr[u].rc, d + 1, mid + 1, R, ql, qr);
    }

    tr[u].cnt = (tr[u].lc ? tr[tr[u].lc].cnt : 0)
              + (tr[u].rc ? tr[tr[u].rc].cnt : 0);
}

void compact(int u, int d) {
    if (!u || (!tr[u].lc && !tr[u].rc)) return;

    compact(tr[u].lc, d + 1);
    compact(tr[u].rc, d + 1);

    ull half = sizeOf(d + 1);

    if (tr[u].lc && tr[u].rc
        && tr[tr[u].lc].cnt == half
        && tr[tr[u].rc].cnt == half) {
        tr[u].cnt = (unsigned int)sizeOf(d);
        tr[u].lc = tr[u].rc = 0;
    }
}

void expandFull(int u, int d) {
    if (tr[u].lc || tr[u].rc || d == B) return;

    tr[u].lc = newNode();
    tr[u].rc = newNode();

    if (tr[u].cnt == sizeOf(d)) {
        tr[tr[u].lc].cnt = (unsigned int)sizeOf(d + 1);
        tr[tr[u].rc].cnt = (unsigned int)sizeOf(d + 1);
    }
}

void normalizePair(int u, int v, int d) {
    if (!u) return;

    if (!v) {
        tr[u].match = -1;
        return;
    }

    if (tr[u].match != 0) return;

    tr[u].match = v;
    if (tr[v].match == 0) tr[v].match = u;

    if (!tr[u].lc && !tr[u].rc && !tr[v].lc && !tr[v].rc)
        return;

    expandFull(u, d);
    expandFull(v, d);

    int bit = (K >> (B - 1 - d)) & 1ULL;

    int v0 = bit ? tr[v].rc : tr[v].lc;
    int v1 = bit ? tr[v].lc : tr[v].rc;

    if (tr[u].lc) {
        if (v0) normalizePair(tr[u].lc, v0, d + 1);
        else tr[tr[u].lc].match = -1;
    } else if (v0) {
        tr[v0].match = -1;
    }

    if (tr[u].rc) {
        if (v1) normalizePair(tr[u].rc, v1, d + 1);
        else tr[tr[u].rc].match = -1;
    } else if (v1) {
        tr[v1].match = -1;
    }
}

inline ll C2(ull n) {
    if (n < 2) return 0;
    return n % MOD * ((n - 1) % MOD) % MOD * INV2 % MOD;
}

inline ll C3(ull n) {
    if (n < 3) return 0;
    return n % MOD * ((n - 1) % MOD) % MOD
         * ((n - 2) % MOD) % MOD * INV6 % MOD;
}

ll g1[B + 1], g2[B + 1], g3[B + 1];

void calc1(int u, int d) {
    if (!u || !tr[u].cnt) return;

    int v = tr[u].match;

    if (!tr[u].lc && !tr[u].rc) {
        if (v > 0 && tr[v].cnt)
            dp1[u] = (int)g1[B - d];
        return;
    }

    calc1(tr[u].lc, d + 1);
    calc1(tr[u].rc, d + 1);

    dp1[u] = (dp1[tr[u].lc] + dp1[tr[u].rc]) % MOD;

    if (v > 0 && ((K >> (B - 1 - d)) & 1ULL)) {
        dp1[u] = (dp1[u]
            + (ll)tr[tr[u].lc].cnt * tr[tr[v].lc].cnt
            + (ll)tr[tr[u].rc].cnt * tr[tr[v].rc].cnt) % MOD;
    }
}

void calc2(int u, int d) {
    if (!u || !tr[u].cnt) return;

    int v = tr[u].match;

    if (!tr[u].lc && !tr[u].rc) {
        if (v > 0 && tr[v].cnt)
            dp2[u] = (int)g2[B - d];
        return;
    }

    calc2(tr[u].lc, d + 1);
    calc2(tr[u].rc, d + 1);

    dp2[u] = (dp2[tr[u].lc] + dp2[tr[u].rc]) % MOD;

    if (v > 0 && ((K >> (B - 1 - d)) & 1ULL)) {
        ll add = 0;

        add += (ll)dp1[tr[u].lc] * tr[tr[u].rc].cnt % MOD;
        add += (ll)dp1[tr[u].rc] * tr[tr[u].lc].cnt % MOD;
        add += C2(tr[tr[u].lc].cnt) * tr[tr[v].lc].cnt % MOD;
        add += C2(tr[tr[u].rc].cnt) * tr[tr[v].rc].cnt % MOD;

        dp2[u] = (dp2[u] + add) % MOD;
    }
}

void calc3(int u, int d) {
    if (!u || !tr[u].cnt) return;

    if (!tr[u].lc && !tr[u].rc) {
        dp3[u] = (int)g3[B - d];
        return;
    }

    if ((K >> (B - 1 - d)) & 1ULL) {
        calc2(tr[u].lc, d + 1);
        calc2(tr[u].rc, d + 1);

        dp3[u] = (
            dp2[tr[u].lc] +
            dp2[tr[u].rc] +
            C3(tr[tr[u].lc].cnt) +
            C3(tr[tr[u].rc].cnt)
        ) % MOD;
    } else {
        calc3(tr[u].lc, d + 1);
        calc3(tr[u].rc, d + 1);

        dp3[u] = (dp3[tr[u].lc] + dp3[tr[u].rc]) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n >> K;

    tr.reserve(1500000);
    tr.push_back(Node());

    int root = newNode();

    for (int i = 0; i < n; ++i) {
        ull l, r;
        cin >> l >> r;
        insertInterval(root, 0, 0, (1ULL << B) - 1, l, r);
    }

    compact(root, 0);
    normalizePair(root, root, 0);

    dp1.assign(tr.size(), 0);
    dp2.assign(tr.size(), 0);
    dp3.assign(tr.size(), 0);

    ull pw[B + 1];
    pw[0] = 1;

    for (int i = 1; i <= B; ++i)
        pw[i] = pw[i - 1] << 1;

    for (int i = 0; i <= B; ++i) {
        ull low = (K & (pw[i] - 1)) + 1;
        g1[i] = pw[i] % MOD * (low % MOD) % MOD;
        g2[i] = pw[i] % MOD * C2(low) % MOD;
    }

    g3[0] = g3[1] = 0;

    for (int i = 2; i <= B; ++i) {
        if ((K >> (i - 1)) & 1ULL) {
            ull half = pw[i - 1];
            g3[i] = (2LL * g2[i - 1] + 2LL * C3(half)) % MOD;
        } else {
            g3[i] = 2LL * g3[i - 1] % MOD;
        }
    }

    calc1(root, 0);
    calc3(root, 0);

    cout << dp3[root] << '\n';
    return 0;
}