【题解】「CF241B」Friends

「CF241B」Friends

trie上乱玩.

传送门

异或粽子加强版.

正篇

我们可以先求出第$k$大的异或值$K$（在那之前k*=2，方便处理两个顺序相反的数对产生的贡献），再计算所有比$K$大的异或值的和。

对于求$K$，我们可以建一棵$01trie$，然后在从高到低扫的同时记录每个数当前到达的树点（初始为根），每次用它们计算当前位为$1$的$cnt$，判断$cnt$与$k$的大小关系，并根据结果计算$K$的这一位和更新树点们（？）。

然后我们可以发现，对于一个数$x>K$，一定在二进制下有第$i$位$x$为$1$，$K$为$0$，而第大于$i$位有$x$取值$=$$K$取值。

于是问题变得简单了：同样的方法记录树点，若当前位$K$为$0$，则我们计算当前异或值为$1$对答案的贡献。这个东西是在$trie$上子树进行对答案的计算的，所以可以记录子树里每一位不同取值的个数，但是不太好算QAQ。我们发现可以对原数组排序并按该顺序进行插入，于是子树对应的区间就是连续的，可以在原数组上前缀和简化算法了！于是这道题就过了（。

代码

 大概就和题解里讲的差不多，但细节蛮多的。（借鉴了不少别人博客QAQ

#include <bits/stdc++.h>
#define Ri register int
#define FOR(i, j, k) for(Ri i = (j); i <= (k); i++)
#define DEC(i, j, k) for(Ri i = (j); i >= (k); i--)
#define ll long long int
using namespace std;

const int maxn = 5e4 + 10, maxk = 32, M = 1e9 + 7, iv2 = 5e8 + 4;
int n, a[maxn];
int ch[maxn * maxk][2], lb[maxn * maxk], rb[maxn * maxk], rt, nc;
int sum[maxn][maxk][2], siz[maxn * maxk];
ll m;

inline void insert(int x) {
    if(!rt) rt = ++nc, lb[rt] = 1, rb[rt] = n;
    int k = rt;
    siz[rt]++;
    DEC(d, 29, 0) {
        if(!ch[k][(a[x] >> d) & 1]) ch[k][(a[x] >> d) & 1] = ++nc, lb[ch[k][(a[x] >> d) & 1]] = x;
        k = ch[k][(a[x] >> d) & 1];
        rb[k] = x;
        siz[k]++;
    }
}

inline ll calc(int k, int v) {
    if(!k) return 0;
    ll res = 0;
    DEC(d, 29, 0) {
        ll t = sum[rb[k]][d][((v >> d) & 1) ^ 1] - sum[lb[k] - 1][d][((v >> d) & 1) ^ 1];
        res = (res + t * (1 << d) % M) % M;
    }
    return res;
}

int to[maxn * maxk];

int main() {
    scanf("%d%lld", &n, &m);
    m <<= 1LL;
    FOR(i, 1, n) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    lb[0] = 1, rb[0] = 0;
    FOR(i, 1, n) insert(i);
    
    //get sum[]
    FOR(i, 1, n) {
        FOR(d, 0, 29) {
            sum[i][d][0] = sum[i - 1][d][0] + (((a[i] >> d) & 1) == 0);
            sum[i][d][1] = sum[i - 1][d][1] + (((a[i] >> d) & 1) == 1);
        }
    }
    
    //get k-th xor
    int low = 0;
    FOR(i, 1, n) to[i] = rt;
    DEC(d, 29, 0) {
        ll cnt = 0;
        FOR(i, 1, n) cnt += siz[ch[to[i]][((a[i] >> d) & 1) ^ 1]];
        if(cnt >= m) {
            low |= (1 << d);
            FOR(i, 1, n) {
                to[i] = ch[to[i]][((a[i] >> d) & 1) ^ 1];
            }
        }else {
            m -= cnt;
            FOR(i, 1, n) {
                to[i] = ch[to[i]][(a[i] >> d) & 1];
            }
        }
    }
    
    //Answer!
    ll ans = m % M * low % M;
    FOR(i, 1, n) to[i] = rt;
    DEC(d, 29, 0) {
        int x = (low >> d) & 1;
        if(!x) {
            FOR(i, 1, n) {
                ans = (ans + calc(ch[to[i]][((a[i] >> d) & 1) ^ 1], a[i])) % M;
            }
        }
        FOR(i, 1, n) {
            to[i] = ch[to[i]][((a[i] >> d) & 1) ^ x];
        }
    }
    printf("%lld", ans * iv2 % M);
    return 0;
}