很多题解都提到分割区间的做法，但是复杂度好像都不大会证。

我在这里试着给出一个（不太严谨）的证明，欢迎指正：

考虑如何构造可以卡满这个算法，

我们先在 $1$ 处放一个 $[1,n]$ 的区间操作。

然后，我们在 $1$ 处放 $[1,1]$ 和 $[2,\frac{n + 2}{2}]$ 操作。

那么，我们的 $[1,n]$ 区间就会被割为 $[1,1],[2,\frac{n + 2}{2}],[\frac{n + 2}{2} +1,n]$。

然后，我们可以递归我们的上述操作，如图

最后，这个的时间复杂度就会来到 $O(m\log m)$。

我们无论怎么添加区间操作，只会让分割的区间更快的变小。

而除了这种构造方法外好像都是 $O(m)\sim O(m\log m)$ 的，并且分割区间的操作是独立于贪心异或的操作的，所以用这种方法的最优复杂度应该是 $O(n + m\log m)$。

欢迎大家指正，本人在比赛时使用了这个做法，在赛后才（似乎）证明出来。