题解：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$，子树内部的答案就是递归子问题。