P12829 「DLESS-2」XOR and Inversion

Genius_Star · 2026-11-11 11:43:45 · 题解

牛逼题。

思路：

考虑只要第一种操作怎么做？

本质上是求 \{p_i \oplus x\} 的逆序对数，即 i < j, (p_i \oplus x) > (p_j \oplus x) 的对数。

分析一下，比较 p_i, p_j 时是在二进制下从高到低找到两个数第一个不同的位置，这一位为 1 的要更大一点；当两个数被同时异或 x 时，考虑 x 为 1 的那些位，如果 p_i, p_j 那些位相同，那么它们的差仍然不变，否则会将对应的 0/1 翻转。

于是只需要找到 p_i, p_j 第一个不同的位置 h，当 p_i 这一位是 1 时有贡献；异或上 x 时，因为后面的位都是相同的不影响，所以只需要看 x 的 h 位，如果是 1 的话那么 p_i 这一位要是 0 才有贡献。

于是这样就有了一个大体思路，将所有数建 01trie，对于每个点，考虑预处理出以它为 LCP 时的贡献，具体的，对每个点 u 预处理 w_{u, 0/1} 表示询问的 x 在当前位为 0/1 时的贡献，即根据 0/1 找左子树下标小于/大于右子树的对数即可（称下标为 pos）。

这是一棵满二叉树，所以你暴力 O(siz_u) 枚举下面的点然后 BIT 算贡献就是 O(n^2 2^n) 的；然后再预处理 W_{i, 0/1} 表示深度为 i 的点在 x 这一位是 0/1 的贡献即可 O(n) 回复询问。

再考虑上操作二，你发现本质上是求 \{ p_{i \oplus B} \oplus A\} 的逆序对，此时下标也变了，怎么办？

还是考虑之前的枚举 LCP 的做法，但是此时我们要求的左右子树的逆序对的贡献都会变，你要算 i \in L, j \in R, (pos_i \oplus B) > (pos_j \oplus B)，欸，这不就是之前的那个子问题吗？

对于每个点 u，在这个点上建立一个子树内 pos 的 trie 树，但是此时每个点的下标只有 0/1 了（L/R），然后再仿照之前的做法把 W_{u, 0/1, i, 0/1} 算出来即可（u 上的 trie 深度为 i 时 B 第 i 位是 0/1 的贡献），然后再预处理出 WW_{i, 0/ 1, j, 0/1} 表示 i 层 A 是 0/1 且 B 在 j 是 0/1 的贡献即可 O(n) 询问了。

直接在 trie 上对每个点暴力建 trie 显然不太行，复杂度直接爆了；考虑 T_u，显然是由 T_{lson_u} 把下标全部标为 0 与 T_{rson_u} 每个点下标标为 1 后合并出来的，于是直接上 trie 合并均摊复杂度就是对的。

时间复杂度是 O(n^2 2^n)，空间复杂度都是 O(n2^n) 的；这样会 MLE，卡空间就是动态回收，合并时不要的点扔了回炉重造就是对的，这样实时所有存在的点的并最多就是整的树的大小是 O(2^n) 的。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcountll(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define lowbit(x) ((x) & (-(x)))
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = (1 << 20) + 1, M = 20;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
struct Node{
    int son[2];
    int siz;
}X[N << 2];
int T, n, m, q, op, x, cnt, A, B, all;
int p[N], pos[N], rt[N << 1];
ll W[M][M][2], s[M];
int top;
int stk[N];
inline int newnode(){
    int k = 0;
    if(top)
      k = stk[top--];
    else
      k = ++cnt;
    X[k].siz = X[k].son[0] = X[k].son[1] = 0;
    return k;
}
inline void ins(int &k, int v, int dep){
    if(!k)
      k = newnode();
    ++X[k].siz;
    if(dep < 0)
      return ;
    ins(X[k].son[(v >> dep) & 1], v, dep - 1);
}
inline int merge(int x, int y, int dep){
    if(!x || !y)
      return x | y;
    // if(all == 1)
    //   cerr << x << ' ' << y << ' ' << dep << '\n';
    assert(dep >= 0);
    W[all][dep][0] += 1ll * X[X[x].son[1]].siz * X[X[y].son[0]].siz;
    W[all][dep][1] += 1ll * X[X[x].son[0]].siz * X[X[y].son[1]].siz;
    X[x].son[0] = merge(X[x].son[0], X[y].son[0], dep - 1);
    X[x].son[1] = merge(X[x].son[1], X[y].son[1], dep - 1);
    X[x].siz += X[y].siz;
    stk[++top] = y;
    return x;
}
inline void print(int x){
    if(!x)
      return ;
    // cerr << x << ' ' << X[x].son[0] << ' ' << X[x].son[1] << ' ' << X[x].siz << '\n';
    print(X[x].son[0]);
    print(X[x].son[1]);
}
inline void build(int k, int l, int r, int dep){
    if(l == r){
        ins(rt[k], pos[l], n - 1);
        return ;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid, dep - 1);
    build(k << 1 | 1, mid + 1, r, dep - 1);
    all = dep;
    // if((l == 2 && r == 3) || dep == 1){
    //     cerr << "L\n";
    //     print(rt[k << 1]);
    //     cerr << "R\n";
    //     print(rt[k << 1 | 1]);
    // }
    s[all] += (1ll << (dep << 1));
    rt[k] = merge(rt[k << 1], rt[k << 1 | 1], n - 1);
}
inline void solve(){
    cnt = A = B = top = 0;
    n = read(), m = (1 << n), q = read();
    for(int i = 0; i < (m << 1); ++i)
      rt[i] = 0;
    for(int i = 0; i < n; ++i){
        s[i] = 0;
        for(int j = 0; j < n; ++j)
          W[i][j][0] = W[i][j][1] = 0;
    }
    for(int i = 0; i < m; ++i){
        p[i] = read();
        pos[p[i]] = i;
    }
    // for(int i = 0; i < m; ++i)
    //   cerr << pos[i] << ' ';
    // cerr << '\n';
    build(1, 0, m - 1, n - 1);
    // cerr << W[n - 1][0][0] << '\n';
    while(q--){
        op = read(), x = read();
        if(op == 1)
          A ^= x;
        else
          B ^= x;
        if(!n){
            puts("0");
            continue;
        }
        ll ans = 0;
        for(int i = 0; i < n; ++i){
            ll sum = 0;
            for(int j = 0; j < n; ++j)
              sum += W[i][j][(B >> j) & 1];
            // cerr << i << ' ' << sum << '\n';
            if((A >> i) & 1)
              sum = s[i] - sum;
            // cerr << i << ' ' << sum << '\n';
            ans += sum;
        }
        write(ans);
        putchar('\n');
    }
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}