CF2045J.Xorderable Array

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数数组 $A$ ，包含 $N$ 个元素，记作 $[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)$ -可排序的，其中 $\oplus$ 表示按位异或。

另有一个长度为 $M$ 的整数数组 $X$ ： $[X_1, X_2, \dots, X_M]$ 。求出所有满足 $1 \leq u < v \leq M$ 且数组 $A$ 可以是 $(X_u, X_v)$ -可排序的索引对 $(u, v)$ 的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$ （ $2 \leq N, M \leq 200\,000$ ）。

第二行是数组 $A$ 的 $N$ 个整数，每个数满足 $0 \leq A_i < 2^{30}$ 。

第三行是数组 $X$ 的 $M$ 个整数，每个数满足 $0 \leq X_u < 2^{30}$ 。

输出格式

输出一个整数，表示满足条件的索引对 $(u, v)$ 的数量。

输入输出样例

输入#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]$ ，可以达到 $(1, 1)$ -可排序的要求。
在样例 2 中，通过将数组 $A$ 重新排列为 $[13, 0, 7, 24, 22]$ ，数组 $A$ 可以满足 $(12, 10)$ -可排序条件。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页