3log 做法：不归之人与望眼欲穿的人们

wtc 讲的 $n\log^{3}$ 做法。Orz

给定一个长为 $n$ 的数组 $a$，有 $m$ 次操作，每次操作形如：

$0\le a_i,k\le 2^{30}$，$1\le n,m\le 5\times 10^{4}$。

首先有经典结论：对于一个固定的右端点，只有 $\log_2 a$ 个或和不同的区间。因为左端点越向左，或和每一个二进制位只会由 $0$ 变 $1$，最多变化 $\log a$ 次。

在一棵线段树上，每个节点维护这个节点表示的区间，前缀或和不同的区间，后缀或和不同的区间。

再维护一棵下标为长度，值为或和最大值的线段树，查询时只需要在线段树上二分即可。底层需要用 set 或其它什么东西维护一下，因为可能会有删除操作。

第一棵线段树合并儿子时，将左儿子的后缀和右儿子的前缀两两配对合并，加入到第二棵线段树上。注意这时要记得去重，笔者去重写错获得 $95$ 分，还以为常数太大了。修改时直接递归到底层修改，然后往上合并即可。注意只修改包含修改位置的区间。

分析一下复杂度，下面认为 $n$ 和 $m$ 同阶：建树时有 $O(n)$ 个节点，每一个节点合并出 $O(\log^2)$ 个区间，这些区间在第二棵线段树上修改，每一次修改是 $O(\log n)$ 的：$O(\log n)$ 时间找到对应叶子，$O(\log n)$ 时间插入到底层数据结构中。修改时，由于只对包含修改点的区间进行修改，包含这个点只有 $O(\log^2 n)$ 个区间，故修改复杂度也是正确的。查询是 $O(\log n)$ 的线段树二分。

实际写出来由于常数过大，会 T 掉一个点。可以将第二棵线段树换成一个分块套对顶堆，理论复杂度退化，但由于常数很小，可以通过。

块长越大，询问越快，修改越慢，最后一个点修改非常多，其它点询问多。故块长调大一些能够获得更少的总用时，在块长为 $128$ 时笔者的代码最快。