AT_tupc2024_f Another Long Sequence Inversion

给定非负整数 $L, R, X$，以二进制形式给出。请用二进制输出长度为 $R-L+1$ 的整数序列 $(L \oplus X, (L+1)\oplus X, \dots, R\oplus X)$ 的逆序对数。 其中，$\oplus$ 表示按位异或操作。 一共有 $T$ 组测试数据，分别求出每组的答案。 逆序对数的定义如下：对于数列 $B=(B_1,B_2,\dots,B_M)$，逆序对是满足 $1 \leq i < j \leq M$ 且 $B_i > B_j$ 的整数对的个数。 按位异或的定义如下：对于非负整数 $A,B$，它们的异或 $A \oplus B$ 是指将 $A,B$ 按二进制表示后，每一位如果 $A$ 或 $B$ 在该位上有且只有一个是 $1$，则结果该位为 $1$，否则为 $0$。 例如，$3 \oplus 5 = 6$，二进制表示为：$011 \oplus 101 = 110$。

输入以如下格式从标准输入给出。 > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据的格式如下： > $L$ $R$ $X$

输出共 $T$ 行。第 $i$ 行输出第 $i$ 个测试数据的答案。

## 部分分 对于满足额外约束 $T \leq 3000, R < 2^{30}, X < 2^{30}$ 的数据集，若答案正确可获得 $10$ 分。 ## 样例解释 1 对于第 $1$ 个测试数据，将 $L,R,X$ 转为十进制分别为 $L=5, R=8, X=2$。$(5\oplus 2, 6\oplus 2, 7\oplus 2, 8\oplus 2)=(7,4,5,10)$，所要求的逆序对数为 $2$。 # 数据范围 - $1 \leq T \leq 2 \times 10^5$ - $0 \leq L \leq R < 2^{2\times 10^5}$ - $0 \leq X < 2^{2\times 10^5}$ - 所有输入均为整数 - $T$ 用十进制给出 - $L, R, X$ 用二进制给出，且不含前导多余 $0$（$0$ 例外，视为一位整数） - 单个输入文件中 $R$ 的所有二进制位数之和不超过 $2\times 10^5$ - 单个输入文件中 $X$ 的所有二进制位数之和不超过 $2\times 10^5$ 由 ChatGPT 5 翻译