CF1886F

· · 题解

模拟赛的时候没有看到无解输出 -1。。。

题意相当于是要选两个时间 L,R 来偷两颗钻石，然后每个监控就是一个区间，要求区间都要包含对应编号的点。

数据范围不大，先二分答案一下 R，显然满足单调性。

然后枚举 L，这样内层判定如果可以 O(n) 就行了。

如果没有编号为 3 的区间是简单的贪心，一个区间必然只会出现一次，一个物品可以放到一个区间中，但是一个盒子只能放一个，直接右端点排序，然后放尽量左的位置即可。

只有两种右端点，左端点顺序是无所谓的，放的话用并查集维护一下下一个空的位置即可。

关键是编号为 3 的区间怎么处理，这些区间可能只出现一次，覆盖两个点，或者是两个，分别覆盖两个点。

第一种情况相当于是编号为 1 的区间，左端点选择区间为 [R-s_i,L-1]，第二种情况是拆成两个区间，一个是编号为 1 的 [L-s_i,L-1]，另一个是编号为 2 的 [R-s_i,R-1]。

先把编号为 1 的做掉，然后处理编号为 3 的，最后再去做 2 的。

然后来证明一下这个东西。 首先如果只有一个区间，那肯定是能不拆就不拆，因为拆的情况只是把它的区间变大，还加了个区间，劣。 相当于要尽量不拆会优，然后考虑一下霍尔定理。 右端点情况很少，因此可以分为只选 $L$，只选 $R$，两个都选三种情况，每个区间都对应着左端点的前缀减一，然后减成 $-1$ 就寄。 然后考虑把一个区间从拆变成不拆会发生什么变化。 只选 $L$ 的部分，区间从 $[R-s_i,L-1]$ 变成了 $[L-s_i,L-1]$，相当于是一段长度 $R-L$ 的区间加 $1$。（长度都相同）。 只选 $R$ 的部分，添加了一个区间 $[R-s_i,R-1]$，前缀减一。 两个都选的部分，添加了一个区间 $[L-s_i,L-1]$，前缀减一。 因此注意到，把一些东西拆掉会让后面的情况变得劣一些，而且 $s_i$ 越大，对后面影响越小。 因此从小到大枚举 $s_i$，只选 $L$ 的部分不合法了再去拆就行了。 外面把 $s_i$ 排好序，这样总复杂度 $O(n^2\log n)$。 [code](https://codeforces.com/problemset/submission/1886/228378151)