[ABC308G] Minimum Xor Pair Query
必须知道的性质：
对于三个非负整数 \(x,y,z(x < y < z)\)，有 \(\min(x \bigoplus y,y\bigoplus z)<x\bigoplus z\)。
-
证明
从二进制最高位开始 \(i=\log V\)，对 \(x,y,z\) 进行如下操作：
-
若它们的当前位都两两相同，继续跳到下一位
i--。 -
根据三个数的大小关系，可以得到两种情况：
- \(x_i=0,y_i=0,z_i=1\)
显然，这时有 \(x\bigoplus y<x\bigoplus z\)。
- \(x_i=0,y_i=1,z_i=1\)
有 \(y\bigoplus z<x\bigoplus z\)。
-
有了上述性质，我们只需要维护大小相邻的数的异或和就行了。
开两个可重集。可重集 \(s\) 记录黑板上当前有哪些元素；另一个可重集 \(ans\) 记录 \(s\) 中相邻元素的异或值。
插入删除操作在维护 \(s\) 的同时维护一下 \(ans\) 即可。