← 返回题目列表

Codeforces · 2045/J

J. 可 Xorderable 数组

中文机器翻译题面 查看原题

给定一个由 $$$N$$$ 整数组成的数组 $$$A$$$:$$$[A_1, A_2, \dots, A_N]$$$。

如果可以重新排列 $$$A$$$,使得对于满足 $$$1 \leq i < j \leq N$$$ 的每对 $$$(i, j)$$$,则在重新排列后必须满足以下条件,则数组 $$$A$$$ 是 $$$(p, q)$$$-xorderable: $$$A_i \oplus p \leq A_j \oplus q$$$ 和 $$$A_i \oplus q \leq A_j \oplus p$$$。运算符 $$$\oplus$$$ 表示按位异或。

给你另一个长度为 $$$M$$$ 的数组 $$$X$$$:$$$[X_1, X_2, \dots, X_M]$$$。计算 $$$(u, v)$$$ 的对数,其中数组 $$$A$$$ 为 $$$(X_u, X_v)$$$-xorderable,对于 $$$1 \leq u < v \leq M$$$。

输入

第一行由两个整数 $$$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})$$$ 组成。

输出

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

示例

输入 #1

3 4
0 3 0
1 2 1 1

输出 #1

3

输入 #2

5 2
0 7 13 22 24
12 10

输出 #2

1

输入 #3

3 3
0 0 0
1 2 3

输出 #3

0

注意

示例输入/输出 #1 的说明

通过将数组 $$$A$$$ 重新排列为 $$$[0, 0, 3]$$$,数组 $$$A$$$ 可进行 $$$(1, 1)$$$-xorderable。

示例输入/输出#2 的说明

通过将数组 $$$A$$$ 重新排列为 $$$[13, 0, 7, 24, 22]$$$,数组 $$$A$$$ 可进行 $$$(12, 10)$$$-xorderable。