CF2157G Isaac's Queries 题解

赛时卡 F 导致没看 G，然后第二天有人告诉我题面然后我随便胡了个做法然后过了？

痛失上紫机会。

异或考虑拆位，由于询问的是最高位考虑从高到低做。我们用 表示 的第 位，下标从 开始。

我们考虑一个询问实际上给了我们什么信息。假设对 的询问是 ，那么

• 的异或和为 。
• 对于任意 ， 的异或和为 。

利用区间询问来确定序列信息和 AT_abc238_e 和 P5937 很类似。所以我们使用类似的方法。

由于询问相当于给了 的一个区间异或和，我们使用前缀和将区间和转化成两个数的关系（毕竟，两个数的关系比多个数的关系简单多了）。

考虑 的前缀和 ，也就是 。我们将一次询问的信息转化为了

• 。
• 对于任意 ，。

之间是否有关系是具有传递性的，换句话说，假设我们知道了 和 和异或和和 和 和异或和，那么 和 的异或和也是已知的。

如果我们将每个 对应到一个点，对于每个已经知道关系的 和 ，我们在 之间连一条边，权值为两个数的异或和，那么两个 关系已知当且仅当两个对应的点在同一个连通块中，并且权值就是路径上边权的异或和（显然根据题意，如果存在多条路径，那么每条路径的异或和一定是相等的）。这两个值可以使用带权并查集维护。

由于每两个点的异或和对应了原数组一个区间的异或和，我们最终的目标是让原数组每个区间的异或和已知，因此我们希望这张图的所有点联通。我们要想在两个点连边只能通过一次代价为区间长度的询问，显然我们希望用尽可能小的代价让整张图联通，因此我们可以跑一个最小生成树。对于异或和为 的询问，答案已经在这一层确定，并且询问也不能给更低层的图连边，在接下来的答案计算中就没用了。因此我们只保留异或和为 的点对，到下一层继续跑最小生成树即可（实际上，我们并不需要让每个点都联通，我们只需要让剩下每个询问的两个点联通即可）。

实际上，每个区间的异或和第 位为 和 的概率十分相近，因此每次询问期望的连边数量是基本一样的，因此这个方法比较优，实测平均每次也不到 。

接下来说一下我对期望代价的粗略估计：

考虑每层保留到下一层的子图是什么样子的。显然，假设异或前缀和第 位的值是 之间在下一层会互相连边，是 的也会两两连边，因此在下一层这个图变成了两个团。由于 和 每层是随机分布的，我们认为在 层之后就只剩下 个连通块了（也就是，所有边都消失了）。

由于数据随机生成，我们认为每组的个数是差不多的。第 层每组有大概 个点。

考虑最后的 MST 会长什么样子。显然就是每组的第一个和最后一个连边，然后中间每个点向两边离自己更远的点连边。

首先最长的边就是每组点的下标极差。考虑从 个点随机选 个点的期望极差是 。对于剩下的点。我们考虑最极端的情况，点都在区间的中间分布，也就是距离两边的长度为 。

我们使用这样一个 python 代码估计代价的大小：

total = 0
for i in range(0, 6):
    n = 100
    delta = (n - (1 << i)) / (n + (1 << i)) * n
    print(delta)
    ans = 0
    ans += 1 / delta
    for j in range(1, int((n / (1 << i)) / 2)):
        ans += (1 / (delta / 2 + j)) * 2
    print(ans)
    total += ans * (1 << i)

print(total)

结果大概是 。在实际询问中一次询问可能带来不止一条边，因此实际平均值可能更小。

参考代码在这里。