首先原题意可以转化为对于每一个 \(1\leqslant k \leqslant n\)，选择 \(k\) 个点染黑，使得给定区间中全白的区间尽量少。
这其实是非常强的，考虑基于四边形不等式的一类区间划分类问题，其区间代价函数可以写为 \(F(l,r)=\sum_{i=l}^{r}\sum_{j=i}^{r}G(i,j)\)，可以化为 \(G(l,r)=F(l+1,r)+F(l,r-1)-F(l+1,r-1)-F(l,r)\)，由于其满足四边形不等式，所以 \(F(l+1,r)+F(l,r-1)\geqslant F(l,r)+F(l+1,r-1)\)。即当 \(F\) 均为整数时四边形不等式问题都可以转化为将 \([1,n]\) 划分成 \(k\) 个区间使得每一段区间内的给定子区间个数和尽量小，如果将每一个 \(l=r\) 的区间事先选中(因为其一定会选中)，其他区间从 \([l,r]\) 变成 \([l,r-1]\)，那么就和原问题一样了。所以满足四边形不等式的整函数的区间划分类问题都可以规约到该问题，并且可以对于每一个 \(1\leqslant k \leqslant n\) 的 \(k\) 求答案。
原问题直接做可以用凸包 \(+\) 并查集维护决策单调性做到 \(O(m\sqrt n\alpha(n))\)，但很难进一步优化。考虑对此施加对偶，对偶完之后相当于选择一些区间进行加 \(1\) 操作，令最终得到的序列的最大值为 \(x\)，选择的区间个数为 \(cnt\)，求 \(kx+m-cnt\) 的最小值。实际上我们只需要对于每一个 \(x\) 求出最多能选多少个区间，最后实际上就是一个斜率优化的形式。
而该问题具有决策单调性，即令 \(i\) 的答案区间集为 \(S_{i}\)，则 \(S_{i-1}\subset S_{i}\)，每次从 \(i-1\) 的结果的结果开始跑，每次取 \(r\) 最小的合法区间即可。直接暴力找是 \(O(nk)\) 的，但如果我们令 \(x\) 为当且已经取到限制上限的最大位置，则接下来加入的 \(l\) 一定 \(>x\)，这是由于我们是按右端点从小到达假如的，\(r<x\) 的区间之前必然已经被考虑到了，所以无需考虑，可以拿线段树维护做到 \(O(m\log n)\)。
实际上对于满足四边形不等式划分的问题，我们可以通过此方法做到 \(O(n^2)\) 或 \(O(nkt)\)(\(t\) 为修改求解操作的所需代价，与 \(F\) 函数本身的性质有关，如当 \(F\) 表现为区间逆序对时，\(t=\log n\)，如果 \(F\) 能够 \(O(1)\) 求解，则 \(t\) 比 \(O(\log n\)) 小) 或 \(O(F(1,n)\log n)\) 的复杂度，更多的时候是在 \(F(1,n)\) 很小的时候表现出其优势。