20250901

当华美的叶片落尽,生命的脉络才历历可见

[ARC085F] NRE

可以看作最大化 $\sum_{i=1}^n [a_i=b_i]$,初始的答案是 0 的个数。考虑赋值操作对答案的影响,原来为 0,贡献就是 -1,原来是 1,贡献就是 1,记为 $c_i$。所以问题就转换为可以使得一个区间的元素都被选择,要使得最后被选择的所有元素的权值和最大。

那就有点类似背包了,但是会有交集的问题,所以考虑按右端点排序,分类讨论。令 $f_i$ 表示将第 $i$ 个区间作为结尾的最大权值和。那么就有两种情况。

  1. 两个区间无交集,可以直接转移,$f_i=f_j+S_{r_i}-S_{l_i-1}$
  2. 区间有交集,但不能有完全覆盖,$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 分治就可了。
Astatinear
“ 一眼,是翩若惊鸿, 二人,是相见倾心, 三生,是再续前缘。 ”
 喜欢文章
2人喜欢
头像