P15677 [ICPC 2024 Jakarta R] Xorderable Array

给定一个包含 $N$ 个整数的数组 $A$：$[A_1, A_2, \dots, A_N]$。 如果可以通过重排 $A$，使得对于所有满足 $1 \leq i < j \leq N$ 的 $(i, j)$ 对，在重排后都满足以下两个条件：$A_i \oplus p \leq A_j \oplus q$ 且 $A_i \oplus q \leq A_j \oplus p$，则称数组 $A$ 是 **$(p, q)$-xorderable** 的。其中运算符 $\oplus$ 表示按位异或。 给定另一个长度为 $M$ 的数组 $X$：$[X_1, X_2, \dots, X_M]$。请计算满足 $1 \leq u < v \leq M$ 且数组 $A$ 是 $(X_u, X_v)$-xorderable 的 $(u, v)$ 对的数量。

第一行包含两个整数 $N$ $M$（$2 \leq N, M \leq 200\,000$）。 第二行包含 $N$ 个整数 $A_i$（$0 \leq A_i < 2^{30}$）。 第三行包含 $M$ 个整数 $X_u$（$0 \leq X_u < 2^{30}$）。

输出一个整数，表示满足 $1 \leq u < v \leq M$ 且数组 $A$ 是 $(X_u, X_v)$-xorderable 的 $(u, v)$ 对的数量。

**样例输入/输出 #1 的解释** 数组 $A$ 是 $(1, 1)$-xorderable 的，可以通过将数组 $A$ 重排为 $[0, 0, 3]$ 来实现。 **样例输入/输出 #2 的解释** 数组 $A$ 是 $(12, 10)$-xorderable 的，可以通过将数组 $A$ 重排为 $[13, 0, 7, 24, 22]$ 来实现。 翻译由 DeepSeek V3.2 完成