2024.3 做题记录

222. CF1936D Bitwise Paradox

和 CF1004F Sonya and Bitwise OR 很像。

考虑一次询问怎么做。考虑分治，每次只计算左端点在 \([l, mid]\)，右端点在 \([mid + 1, r]\) 的区间的贡献。对于每个 \(i \in [l, mid]\)，维护最小的 \(j \in [mid + 1, r]\) 使得 \([i, j]\) 的或 \(\ge v\)，那么 \(\max\limits_{k = i}^j a_k\) 对答案有贡献。

考虑带修怎么做。考虑套上线段树，利用线段树的分治结构，问题变成了如何合并两个区间的答案。

按位或有个很好的性质，就是前（或后）缀的或只会变化 \(O(\log V)\) 次。所以我们对于线段树上每个结点，维护前缀和后缀的或第一次变化的位置。

计算左端点在左结点，右端点在右结点的区间贡献，就枚举左结点所有后缀或第一次变化的位置作为左端点，双指针维护使得区间或 \(\ge v\) 的最靠左的右端点即可。

注意到 \(a\) 不变，可以使用 ST 表单次 \(O(1)\) 计算 \(a\) 的区间最大值。合并两个区间的复杂度为 \(O(\log V)\)。所以总时间复杂度为 \(O((n + q) \log n \log V)\)。