JOISC 2017 D

· · 题解

神题，模拟赛考到，不会，遂题解诞生。

读完题目，发现等价于给出若干 [l_i,r_i],c_i，需要将 c_i 分为 k,c_i-k 两部分加到 [l_i,r_i] 亦或 [1,l_i)\cup (r_i,n]，要求最小化最后每个位置的值的最大值。

可以考虑一个调整法的思路，我们先假定全部分给 [l_i,r_i]，得到当前的解 p_i，同时将 c_i 拆分为 c_i 个 l_i,r_i 相同且 c_i=1 的询问。

问题就变成给出一个集合，元素为区间，而我们现在需要从中找到一个最优秀的子集 S，使得将 \forall [l_i,r_i]\in S 拆为 [1,l_i-1],[r_i+1,n] 后最大值最小。

我们称这个拆解的过程为“反转”。

我们设这个拆分后每个位置上的值是 q_i，那么会发现一些性质。

性质零

设最优答案为 ans，则我们声称 [ans,\sum c] 都是存在方案的。

证明是显然的， i 的一个没有覆盖最大值的区间覆盖过去就好了。

性质一

可以发现，若 I_1,I_2\in S，且 I_1\cap I_2=\varnothing，则 S 并非最优。

证明：考虑此时我们不反转 I_1,I_2，则会让 q 产生如下变化：

  1. i\in I_1\cup I_2,q_i\leftarrow q_i
  2. i\notin I_1\cup I_2,q_i\leftarrow q_i-2

这样的变化一定不劣。

由此可以得到：一定存在最优集合 S，满足 S 里所有区间的交集不为空。

形式化地，有：\max_{[l_i,r_i]\in S}l_i\le \min_{[l_i,r_i]\in S}r_i

下面我们称 I=[\max_{[l_i,r_i]\in S},l_i,\min_{[l_i,r_i]\in S},r_i]

现在我们来考虑在多项式复杂度内解决本问题。

设 z_i=\sum_{[l_i,r_i]]\in S}[i\in [l_i,r_i]]，也就是包含它的元素个数。

那么有 q_i=p_i+(|S|-z_i)-z_i=p_i-2z_i+|S|。

设某个 t\in I，则 z_t=|S|。

考虑二分答案，设当前二分答案为 limit，如果合法的充要条件是什么呢？

也就是 \exists S,t,\max q_i\le limit。

注意到我们在计算过程中只关心 |S|，也就是 z_t，不妨枚举 t,z_t，那么会有：\max (p_i-2z_i+z_t)\le limit\implies z_i\ge \lceil\frac{p_i+z_t-limit}{2}\rceil。

考虑构造这样一个 S，可以想到一个显然正确的贪心算法：依次扫描 i:1\to t，并开一个优先队列，维护当前待使用的所有区间，按照 r 排序，当前发现 z_i 不足，那么就贪心地选大的 r 填上去。

最后再判断 t+1\to n 的 z 是否符合即可。

复杂度 O(n^2m\log m\log V)。

注意到复杂度主要开销是 (t,z_t) 的枚举。

性质二

我们断言，如果最优解不是 S=\varnothing，那么一定有 \exists t,S,\max_{i\in I}q_i\ge \max_{i}q_i-1,\max_{i}q_i\le limit。

考虑如下当 \max_{i\in I} q_i<\max_iq_i-1 时对 S 的调整：

以下操作只要 S 不为空且条件不满足持续进行。

  2. 否则考虑取到 I 的两个集合，也就是 r_{\min},l_{\max} 所在的两个区间 A,B，将其删去，那么有 \forall i\in I,q_i'\leftarrow q_i+2，其余 q_i 不变，也可以将差距缩小 2。

可以发现操作始终可以进行，因此最终必然可以操作到满足条件，或者 S=\varnothing。

注意到我们可以钦定 t 为取到 \max_{i\in I}q_i 的 i，因为 I 中的点对于 S 这个方案而言是等价的。

由此，我们可以知道 \max_{i\in I}q_i=q_t\ge \max_{i}q_i-1，而由性质零和构造方法，只要有解，那么我们就可以强化为构造出一个正好答案是 \max_iq_i=limit 的解，因此 limit\ge q_t=p_t-z_t\ge limit-1，因此对于 t，我们仅需枚举 p-limit(+1) 这两个即可。

复杂度降到 O(n^2\log m\log V)。

性质三

我们断言，如果最优解 S\neq \varnothing，那么一定是有某个最优的 S,t，满足 p_t=\max p_i。

注意到这个 t 同样取到了 \max_{i\in I}q_i，因此有：

q_t=p_t-z_t\ge \max_iq_i-1\ge \max_i(p_i-2z_i+z_t)-1\ge \max(p_i-z_t+[i\notin I])-1

这推出 p_t\ge \max(p_i+[i\notin I])-1\implies p_t=\max p_i。

性质四

更强于性质三的，我们给出，如果最优解不是 S=\varnothing，那么存在最优解 S，任意 \lbrace t|p_t=\max_{i}p_i\rbrace\subseteq I 。

设一个 x,p_x=\max p_i，则 q_x=p_x+|S|-2z_x\le ans\le p_x-|S|+1\implies 2|S|-2z_x\le 1。

由于左边是偶数且非负，所以只能取到 z_x=|S|，因此 x\in I。

综合各个性质，我们仅需 2 次贪心算法就可以判断了。