题解：CF2157G Isaac's Queries

· · 题解

对 a_i 做前缀和得到 s_i，每次询问变成 f(u,v)=\left\lfloor\log_2(s_u \operatorname{xor} s_v)\right\rfloor。

首先考虑只有 0/1 怎么做，钦定 s_0=0，那么有 s_n=[f(0,n)=0]。同理，对于 0<i\leq \frac{n}{2} 的 s_i 询问 f(i,n) 可以代价更小地得到答案；对于 \frac{n}{2}<i<n 的 s_i 询问 f(0,i)。这样我们得到了所有 s_i 的值，直接计算 \frac{n(n+1)}{2} 个询问即可。

然后考虑原问题。考虑拆位，假设当前计算到第 d 位，钦定 s_0 这一位是 0，使用类似的方法我们能知道 s_i 这一位值是多少。接下来像字典树一样我们分成左右两棵子树，两棵子树之间点的答案就是 d，子树内部的答案就是递归子问题。

350449040