Loj#6507. 「雅礼集训 2018 Day7」A

题意 ： 维护一个长为 的序列 ，支持下列操作 :

• 区间或
• 区间与
• 区间求

，时限 。

---

Seg-Beats。

对于每个节点，记录区间 。

• 与 ：

  • 若区间 ，则无影响，直接返回。

  • 若 ，则操作后区间内是清一色的，打标记维护。

  • 对于其他情况，暴力递归。

• 或 ：

  • 若区间 ，则无影响，直接返回。

  • 若 ，则操作后区间内是清一色的，打标记维护。

  • 对于其他情况，暴力递归。

考虑复杂度，我们发现一次暴力递归必定使得区间内的某一非纯色位变为纯色。

将节点的势能定义为非纯色位的数目。一个节点的势能上界为 ，每次暴力会使得势能减少一。每次修改会使得 个点的势能不可预期地变化。总复杂度为 。