前言

好难，完全想不到。

思路

首先我们先把假设所有区间都用第一个操作，然后考虑从

1

操作变成

2

操作，就是会进行一次全局加

1

然后把

l\sim r

中的数减

2

然后我们就把操作全部转化为减法了，但是我们发现还有全局加，考虑枚举全局加的次数

k

然后就好做了对于一个数

i

如果不满足条件则我们拿出

l_j\leq i

的最大的

r_j

然后进行一次区间减法即可，可是复杂度是

n^2\log^2(n)

的，考虑优化。

冥思苦想半天发现不会优化，通过看题解得知原来是

k

只用判断

O(1)

个，首先我们二分答案

mid

那么可以证明

k

的下限为

mx-mid

其中

mx

为原序列的最大值，然后我们称

k

满足条件为可以通过

k

次操作把原序列的最大值降到

\leq mx-k

，然后我们考虑如果

k

合法则

k-2

一定合法，如何证明呢。

如果这 $k$ 个区间不存在公共交集，那么拿出没有交集的两个区间 $i,j$ 则我们把 $i,j$ 删掉之后对最大值的影响不会超过 $2$ 则可证出。
如果这 $k$ 个区间存在公共交集，然后我们拿出 $k$ 个区间中的两个使得这两个区间的交恰好为总共的交，然后将这两个区间删除，对于交的部分我们相当于 $+2$ 对于交之外的显然波动不会比交的部分更大所以也可以证明对最大值的影响不会超过 $2$ 。

那么对于二分的

mid

我们先假定

k=mx-mid

那么如果

k,k+1

都不合法也不可能存在

k+d,d>1

合法了，时间复杂度

O(n\log^2(n))

。

代码很短就不给了，想要私信我。