题解 CF2247D1 XOR Sorting (Easy Version)
JuRuoOIer
·
·
题解
题解 CF2247D1 XOR Sorting (Easy Version)
其他题
这个位置放线段树而且只评了 *2000（Clist）是我完全没想到的，我还以为我做麻烦了。
题意
给定长为 n 的数组 a，q 次单点修改，操作前及每次操作后回答：如果每次只能交换两个异或和不超过 k 的下标，则将 a 排序所需的 k 至少是多少？
数据范围：多测，\sum n,\sum q\le 10^6。D1 中 q=0。
做法
:::info[我毫无头绪。]
若知道了 k，则每个数可交换的范围是什么？
:::
:::info[我分析出来了，但是我不知道这有什么用。]
:::
以下所有“位”指二进制位，所有 $\log$ 默认下取整。二进制位是从低往高，用 $0$-index 编号的。
对于一个 $k$，由于异或不会使位数增多，所以首先前 $2^{\log k}$ 个数是可以随便换的。与此类似，当第 $\log k$ 及更高位完全相同时异或就没了，所以每个 $[p2^{\log k},(p+1)2^{\log k})$ 都是可以随便换的。
除此以外，第 $2q$ 段和第 $2q+1$ 段间也可以随便换，因为只要后 $\log k$ 位是相同的，前面位异或为 $2^{\log k}$，就可以交换；而我们可以利用段内随便换的性质，把所有想交换的数放到对应的位置。
所以 $k$ 对范围的影响只与 $\log k$ 有关，所以 $k$ 一定是 $2$ 的幂。
所以 D1 直接枚举 $k$ 就行了，D2 维护一个类似线段树的结构，但是是按段分左右儿子的（可以视为把 $n$ 补到了 $2^{1+\log (n-1)}$），然后对于每个点维护其 $\max$ 和 $\min$ 就可以知道某个点的左右儿子之间有没有逆序对，进而求出答案了。
D2 的单组复杂度是 $O(q\log n)$。