当华美的叶片落尽,生命的脉络才历历可见
[ARC085F] NRE
可以看作最大化 $\sum_{i=1}^n [a_i=b_i]$,初始的答案是 0 的个数。考虑赋值操作对答案的影响,原来为 0,贡献就是 -1,原来是 1,贡献就是 1,记为 $c_i$。所以问题就转换为可以使得一个区间的元素都被选择,要使得最后被选择的所有元素的权值和最大。
那就有点类似背包了,但是会有交集的问题,所以考虑按右端点排序,分类讨论。令 $f_i$ 表示将第 $i$ 个区间作为结尾的最大权值和。那么就有两种情况。
- 两个区间无交集,可以直接转移,$f_i=f_j+S_{r_i}-S_{l_i-1}$
- 区间有交集,但不能有完全覆盖,$f_i=f_j+S_{r_i}-S_{r_j}$ 考虑形式化这些限制条件。第一个就是 $r_j <l_i\leq r_i$,第二个是 $r_j\leq r_i$、$r_j\geq l_i$ 并且 $l_j<l_i$。发现是个三维偏序,所以无脑 CDQ 分治就可了。