问题的分析

常见套路

正难则反

[Chengdu Regional 2025] K-Coverage

Portal。如果直接枚举删除哪条线段，然后求解把它放在哪，可能不是很好做。不妨直接扔进去一条新的线段，不断移动它，然后看删除哪个线段最优。维护删除所有线段的贡献 $delta_i$，每次移动线段只会对一个连续段的线段的 $delta$ 造成改变。代码。

操作的转化

[qoj962] Thanks to MikeMirzayanov

Portal.

操作好像不是很方便，但是可以用两次操作实现对每一段分别翻转（即一次正常分一次全局）。于是问题就可以在值域上分治下去了（因为段之间互不影响），我们只需要对 01 排序，这是容易的，只需要不断地对间隔的 10 段来排序，$O(\log n)$ 即可完成。注意不要每次操作后直接全局翻转使得你的常数乘二。代码。

例题

刷基础

[Ptz Winter 2020 Day3] Disjoint LIS

Portal.

看上去非常 NP，