085F

题目描述 一个全部为 \(0\) 的数组 \(a\) 。给01数组 \(b\) 和 \(q\) 个操作，每个操作 \(l_i,r_i\) ，即将 \(a\) 的 \([l_i,r_i]\) 全部赋值为 \(1\) ，你可以选一些操作，不要一些操作，求最后 \(a\) 和 \(b\) 最少有多少位不同 ......

一眼顶针，鉴定为 **implement** 不足，我写不出来。 先通过 Trick 转化 $a_i = 0 \to -1，a_i = 1 \to 1$。 那么显然把 $[l, r]$ 全部摊为 1 的贡献就是 $a_{l \to r}$。转化为 n - 最大贡献。 然后我们可以转化以下。 $$f_ ......

# [[ARC085F] NRE](https://www.luogu.com.cn/problem/AT_arc085_d) 首先这道题要先将区间**按左端点排序**。我们先不考虑区间重叠的情况。 令 $f_i$ 表示前 $i$ 个区间已经决策好是否选择，而且**第 $i$ 个区间必选**的情况下 ......