题解：CF2103F Maximize Nor

· · 题解

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

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

  1. 形如 000\cdots0 的序列权值取决于 0 的个数的奇偶性。
  2. 形如 ???\cdots1 的序列权值始终是 0。

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

  1. 如果序列不存在数字 1 ，归纳成结论 1。
  2. 否则找到序列中最后一个 1 对它使用结论 2，归纳成情况 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