先考虑\(E1\) 只需要删除两条线使得不被覆盖的点数最多。
观察到点数只有\(200000\) 那么我们完全可以先将被至少\(3\)条线覆盖的点删掉。
考虑枚举一条线，枚举这条线覆盖的点寻找另外一条线覆盖这些点中的最大值，然后再找没覆盖这些点之外的线的最大值即可。
复杂度容易证明是线性的。
考虑\(E2\) 需要我们删除\(k,k\le 10\)条线求出不被覆盖的点数最多。
点的数量不变，遇到这种贪心没办法解决的问题，由于点的规模很大，也不能使用网络流，只能考虑\(dp\)。
设状态\(f_{i,j}\)表示前\(i\)个点且第\(i\)个点必无覆盖已经删掉\(j\)条线的最大值。
考虑枚举上一个未被覆盖的点\(k\) 设包含\(i\)的线段数量-包含\(i\)包含\(k\)的线段数量为\(v\) \(f_{i,j}=max\{f_{k,j-v}\}\)
我们可以先把那些被覆盖超过\(10\)次的点扔掉。
这样上述转移是\(n^2k^2\)的或者优化一步为\(n^2k\)的。
考虑进一步优化这个转移式无非是求最大值
利用线段树维护即可。
注意到我们需要外层枚举\(j\) 还需要不断更改\(f{k,j-v}\)这个东西，可以暴力的修改。
因为最多修改\(nk\)次。
总复杂度\(nklogn\)。
- Codeforces Doremy Drying Round Plancodeforces doremy drying round version doremy drying plan version doremy drying 1889c version doremy drying 1889 题解version doremy drying connecting doremy 1889 plan connecting doremy 1890d plan version报告doremy drying connecting doremy plan 39 codeforces pegging global doremy