J. 可排序数组 详细题解

问题重述

给定数组 $A$（长度 $N$）和数组 $X$（长度 $M$）。对于每一对 $(u,v)$（$1\le u<v\le M$），判断 $A$ 是否可以通过重新排列成为 $(X_u,X_v)$-可排序的，即重排后对所有 $i<j$ 满足：

$$A_i \oplus X_u \le A_j \oplus X_v \quad\text{和}\quad A_i \oplus X_v \le A_j \oplus X_u $$

求满足条件的 $(u,v)$ 对数。

---

核心观察

1. 成对可排序性条件
   对于两个数 $B_0,B_1$，考虑它们能否被“排序”使得同时满足上述两个不等式。通过逐位分析（从高位到低位）可得：
   设 $P,Q$ 为两个参数，则 $(B_0,B_1)$ 是可排序的当且仅当

   $$P \oplus Q \le B_0 \oplus B_1$$

   其中“可排序”指存在一种顺序（$B_0$ 在前或 $B_1$ 在前）使得两个不等式成立。

2. 扩展到整个数组
   对整个数组 $A$ 而言，要存在一种重排使得所有元素对 $(i,j)$ 都满足条件，等价于要求 任意两个元素 $A_i,A_j$ 都满足

   $$P \oplus Q \le A_i \oplus A_j$$

   因为最严格的限制来自异或值最小的那一对。令

   $$\text{minXOR} = \min_{i<j} (A_i \oplus A_j)$$

   则 $A$ 是 $(P,Q)$-可排序的当且仅当

   $$P \oplus Q \le \text{minXOR}$$

3. 充分性
   当 $P \oplus Q \le \text{minXOR}$ 时，可以通过将 $A$ 按照 $A_i \oplus (P \& Q)$ 的值排序，即可满足所有条件。因此该条件是充要的。

---

算法步骤

1. 计算 $\text{minXOR}$
   将 $A$ 排序，则最小异或值一定出现在相邻元素之间。计算 $\min\limits_{i=1}^{N-1} (A_i \oplus A_{i+1})$，复杂度 $O(N \log N)$。

2. 统计满足 $X_u \oplus X_v \le \text{minXOR}$ 的无序对 $(u,v)$ 个数
   使用二进制 Trie 树（每个节点记录经过该节点的数值个数）。

   • 依次处理每个 $X_i$，在插入之前，查询 Trie 中已有数值与 $X_i$ 异或值 $\le \text{minXOR}$ 的个数。
   • 查询时按位从高到低，利用 $\text{minXOR}$ 的二进制位控制分支：
     设当前位为 $b$（从最高位到最低位），设 $\text{lim}$ 为 $\text{minXOR}$ 的当前位。
     对于 $X_i$ 的当前位 $x$，在 Trie 中走与 $x$ 相同的方向时，异或值的当前位为 $0$，若 $\text{lim}=1$，则还需加上相反方向子树的所有值（因为异或值为 $1$ 的路径若 $\text{lim}=1$ 则后续任意均可）。
     具体实现时递归或迭代均可。
   • 查询后将 $X_i$ 插入 Trie。
     最终累加得到的个数即为满足 $X_u \oplus X_v \le \text{minXOR}$ 的对数，即为答案。

3. 复杂度

   • 排序 $O(N \log N)$。
   • Trie 操作 $O(M \cdot \log \max X) \le O(M \cdot 30)$，总复杂度 $O(N \log N + M \log X)$，满足 $N,M\le 2\times 10^5$。

---

参考代码

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

const int B = 30; // 因为 Ai, Xi < 2^30

struct TrieNode {
    TrieNode* child[2];
    int cnt;
    TrieNode() : child{nullptr, nullptr}, cnt(0) {}
};

void insert(TrieNode* root, int x) {
    TrieNode* cur = root;
    for (int i = B-1; i >= 0; --i) {
        int b = (x >> i) & 1;
        if (!cur->child[b]) cur->child[b] = new TrieNode();
        cur = cur->child[b];
        cur->cnt++;
    }
}

int query(TrieNode* root, int x, int limit) {
    // 返回 trie 中与 x 异或值 <= limit 的数的个数
    TrieNode* cur = root;
    int ans = 0;
    for (int i = B-1; i >= 0; --i) {
        if (!cur) break;
        int xb = (x >> i) & 1;
        int lb = (limit >> i) & 1;
        if (lb == 1) {
            // 当前位异或值为 0 的路径全部符合（因为后续任意都小于 limit）
            if (cur->child[xb]) ans += cur->child[xb]->cnt;
            // 走异或值为 1 的路径继续判断
            cur = cur->child[xb ^ 1];
        } else {
            // lb == 0，只能走异或值为 0 的路径
            cur = cur->child[xb];
        }
    }
    if (cur) ans += cur->cnt; // 完全相等的情况
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<int> X(M);
    for (int i = 0; i < M; ++i) cin >> X[i];

    // 计算 minXOR
    sort(A.begin(), A.end());
    int minXOR = INT_MAX;
    for (int i = 0; i < N-1; ++i) {
        minXOR = min(minXOR, A[i] ^ A[i+1]);
    }

    // 统计满足 Xi ^ Xj <= minXOR 的无序对
    TrieNode* root = new TrieNode();
    ll ans = 0;
    for (int i = 0; i < M; ++i) {
        ans += query(root, X[i], minXOR);
        insert(root, X[i]);
    }
    cout << ans << '\n';
    return 0;
}