首页 学习笔记

感觉 01trie01trie 也是相当有意思的一个数据结构，这里也不是小 trick，就是记录一些 01trie01trie 的应用。

持续更新中～

# P5283 [十二省联考 2019] 异或粽子

一道经典题目，介绍一个比较简单的做法。

先做一个前缀异或和，题目就变成了找到 si⊕sjs_i \oplus s_j 前 kk 大的点对，且 i<ji < j。

i<ji < j 的条件并不好处理，所以把这个上三角形对称一下，变成完整的矩形，然后就变成了找到前 2×k2\times k 大的点对。

具体操作时，建一个大根堆，对于第 ii 行，把与其异或最大值插到堆中。

每次删除堆顶最大值，假设堆顶是第 ii 行的第 cc 大值，那么就把第 ii 行的第 c+1c + 1 大值再插入堆中。

以此类推，找到前 2k2k 个点对即可，最后答案再除以 2。

时间复杂度 O((n+k)log⁡alog⁡n)O((n + k)\log a\log n)。

# CF241B Friends

是上面那道题加强版。

考虑先把第 kk 大值找到。那么二分第 kk 大值，枚举每一个数，在 01trie01trie 上找到与当前数异或值大于等于 midmid 的个数，最后跟 2k2k 比较大小即可。

这部分时间复杂度 O(nlog⁡2a)O(n\log^2a)，也可以直接 01trie01trie 上二分，但是我不会。

然后要计算所有异或值大于等于 kthkth 的和是多少。

先预处理一个数组 tr[x][y]tr[x][y]，表示在 01trie01trie 上 xx 的子树中 2y2^y 出现了多少次。这样就可以在 O(log⁡a)O(\log a) 的复杂度下计算一棵子树异或一个值的和是多少了。

这部分时间复杂度也是 O(nlog⁡2a)O(n\log^2a)。

小坑点：2×k2\times k 会爆 intint，所以二分 checkcheck 时需要开 longlonglong \ long。

codecode

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int inv2 = 5e8 + 4;
const int N = 5e4 + 10;
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
int n, k, ans;
int a[N];
int ch[N * 20][2], siz[N * 20], tot;
int tr[N * 20][35]; //tr [x][y]: x 的子树中 2^y 出现了几次
inline void ins(int x){
    int u = 0;
    for(int i = 30; i >= 0; --i){
        int t = (x >> i) & 1;
        if(!ch[u][t]) ch[u][t] = ++tot;
        u = ch[u][t], siz[u]++;
    }
}
inline int qry(int x, int v){
    int u = 0, res = 0;
    for(int i = 30; i >= 0; --i){
        int y = (x >> i) & 1, b = (v >> i) & 1;
        if(!b) res += siz[ch[u][y ^ 1]], u = ch[u][y];
        else u = ch[u][y ^ 1];
        if(!u) break;
    }
    res += siz[u];
    return res;
}
inline ll chk(int x){
    ll cnt = 0;
    for(int i = 1; i <= n; ++i) cnt += qry(a[i], x);
    return cnt / 2;
}
inline void dfs(int u, int dep, int z){
    if(!u) return;
    if(!dep){
        for(int i = 0; i <= 30; ++i)
            if((z >> i) & 1) tr[u][i] = siz[u];
        return;
    }
    dfs(ch[u][0], dep - 1, z);
    dfs(ch[u][1], dep - 1, z | (1 << (dep - 1)));
    for(int i = 0; i <= 30; ++i)
        tr[u][i] = tr[ch[u][0]][i] + tr[ch[u][1]][i];
}
inline int qrysum(int x, int kth){
    int u = 0; int res = 0;
    for(int i = 30; i >= 0; --i){
        int y = (x >> i) & 1, b = (kth >> i) & 1;
        if(!b){
            int v = ch[u][y ^ 1];
            for(int j = 0; j <= 30; ++j){
                if((x >> j) & 1) res = add(res + mul((siz[v] - tr[v][j]), (1 << j)));
                else res = add(res + mul(tr[v][j], (1 << j)));
            }
            u = ch[u][y];
        }else u = ch[u][y ^ 1];
        if(!u) break;
    }
    res = add(res + mul(siz[u], kth));
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i], ins(a[i]);
    if(!k) return cout << 0 << endl, 0;
    int l = 0, r = (1 << 30), kth = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid) >= k) kth = mid, l = mid + 1;
        else r = mid - 1;
    }
    dfs(ch[0][0], 30, 0), dfs(ch[0][1], 30, (1 << 30));
    for(int i = 1; i <= n; ++i) ans = add(ans + qrysum(a[i], kth));
    ans = mul(ans, inv2);
    cout << ((ans - mul((chk(kth) - k), kth)) % mod + mod) % mod << endl;
    return 0;
}