[ARC085F] NRE

首先这道题要先将区间按左端点排序。我们先不考虑区间重叠的情况。

令 \(f_i\) 表示前 \(i\) 个区间已经决策好是否选择，而且第 \(i\) 个区间必选的情况下的最小不同数。再令 \(sum_i\) 表示前 \(i\) 个数中 \(1\) 的个数。枚举一个区间 \(j<i\)，可以根据区间 \([l_j,r_j],[l_i,r_i]\) 二者是否有交集来进行分类讨论。这里我们记初始的 \(f_0\) 的答案为全 \(0\) 数组与 \(b\) 的不同数。

• 二者没有交集，那么就是 \(f_i=\min{f_j+(sum_{r_i}-sum_{l_i-1})-[(r_i-l_i+1)-(sum_{r_i}-sum_{l_i-1})]}\)，原因是本来 \(1\) 的位置没有贡献，现在有 \(+1\)，即前面加的一坨，而本来 \(0\) 的位置贡献是 \(+1\) 的，现在变为 \(0\)。化简一下就是 \(f_i=\min{f_j+2(sum_{r_i}-sum_{l_i-1})-r_i+l_i-1}\)。
• 二者有交集，那就相当于增加了 \([r_j+1,r_i]\) 这一部分。将上面的式子改为 \(f_i=\min{f_j+2(sum_{r_i}-sum_{r_j})-r_i+r_j}\)。

这样一个 \(O(N^2)\) 暴力就出炉了。

接下来考虑怎么优化它。

它这些区间，第一类没有交集的可以以 \([j,f_j]\) 为一组插入线段树/树状数组中，然后直接一个区间查询。

第二类有交集的可以先提炼出关于 \(j\) 的式子，插入 \([j,f_j-2sum_{r_j}+r_j]\) 即可，同上。

这样复杂度就是 \(O(N\log N)\)。