题解：CF2103F Maximize Nor

首先考虑只有 $0$ 或 $1$ 怎么做，此时答案变成判断是否存在一个包含 $i$ 的区间权值为 $1$。

注意到对于任意 $x$ 有 $\operatorname{nor} (x,1)=0,\operatorname{nor}(x,0)=x\,\operatorname{xor} \, 1$。那么容易注意到如下结论：

到这里实际上我们已经可以快速计算某一序列的权值了，方法如下：

考虑计算每个区间的权值，枚举右端点，找到右端点前上一个 $1$ 的出现位置，计为 $lst$。那么通过一些简单的讨论，对于每个左端点我们可以 $O(1)$ 计算该区间权值：

对于每个右端点直接找出权值为 $1$ 的左端点最小的区间，做一个区间覆盖问题就能知道每个 $i$ 的答案。

然后考虑一般情况。先拆位，发现每一位的权值按照上面的讨论分成三段。固定右端点，左端点从左到右做一个扫描线状物。注意到每一位的三段权值只有最多四个关键点，那么把每一位的值加起来总共只有 $O(\log V)$ 种不同的权值。直接找出这 $\log V$ 个区间做区间 chkmax，总时间复杂度 $O(n\log V(\log V+\log n))$。

具体细节可以看代码。

https://codeforces.com/contest/2103/submission/316770845