Description：

$0\sim n−1$ 的排列，如果 $p_i\text{ xor }p_j\leqslant a$ 就可以交换 $p_i$ 和 $p_j$ 。求能够排序的最小的 $a$ 。支持交换某对 $p_i$ 和 $p_j$ 。

$1\leqslant n,q\leqslant 10^5$

Solution：

首先我们可以从小到大枚举 $a$ ，并把 $p_i\text{ xor }p_j=a$ 的连起来，那么一个联通块中的所有数都是可以任意交换的，那么如果 $i-1$ 和 $p_i$ 在同一个联通块里，那么答案就是这时的 $a$ ，观察一下发现只有在 $a=2^k$ 的时候才会连边，也就是说答案一定是 $2^k$ 的形式，那么又可以发现这时 $i$ 和 $p_i$ 被连起来当且仅当 $a$ 是 $i\text{ xor }p_i$ 的最高位，于是答案就是 $\max(\text{maxbit}(i\text{ xor }p_i))$ ，用个线段树维护一下就行了。

Code：