题解：切符の手配 (Arranging Tickets)

切符の手配 (Arranging Tickets))
记录一下这道推性质神题。其实是因为这题给我调红温了，反复看错题意+小错误一大堆。
题意

这个题意太难看懂了，放个形式化题意：
有 \(m\) 种区间，第 \(i\) 种区间 \([a_i,b_i]\) 有 \(c_i\) 个。
维护一个初始全为 \(0\) 的序列 \(a\)，对于每个区间 \([l_i,r_i]\)，有两种选择：

• 把 \([l_i,r_i]\) 中的数 \(+1\)。
  
• 把 \([1,l_i)\cup(r_i,n]\) 中的数 \(+1\)。
  

请最小化最终 \(a_i\) 的最大值。
题解

首先二分，接下来只需要 check 答案是否可以为 \(mid\)。
我们先让所有区间都选择第 \(1\) 种操作，令 \(b_i\) 表示此时的 \(a_i\)；\(c_i\) 表示最优方案下的 \(a_i\)。
我们可以将某些区间的操作变为操作 \(2\)（我们称为翻转操作），设为集合 \(S\)。
\(S\) 为空的情况直接判一下即可，下面默认 \(S\) 不为空。
性质一：存在一个最优的 \(S\)，满足集合 \(S\) 中的区间的交一定不为空。

证明：反证法，如果结论不成立，那么 \(S\) 中必然存在某两个区间 \(A,B\) 不相交。
相比于不翻转 \(A,B\)，看一些 \(a\) 序列中的 \(a_i\) 有什么变化：
(1) \(i \in A \cup B\)：不变。
(2) \(i \notin A \cup B\)：\(+2\)。
所以翻转他俩没有任何元素的值会变小，所以肯定不优。

下面我们设区间 \(U\) 表示 \(S\) 中这些区间的交。
设 \(cnt_i\) 表示位置 \(i\) 被 \(S\) 中的区间覆盖的次数。
我们可以枚举 \(U\) 中的某个位置 \(x\)，然后去枚举 \(cnt_x\)，由性质一可知 \(cnt_x=|S|\)。
那么对于 \(i\) (\(i \ne x\))，\(c_i=b_i+cnt_x-2\times cnt_i\)，要满足 \(c_i\le mid\)，即 \(cnt_i\ge \lceil \frac{b_i+cnt_x-mid}{2} \rceil\)。
我们可以根据这个下界去贪心地确定集合 \(S\)，具体地，我们从小到大扫描 \(i\)（\(i\ne x\)）：
如果 \(cnt_i\) 还没有抵达下界，那么就在所有还没选过的包含 \(i\) 且包含 \(x\) 的区间中选一个右端点最大的区间加入 \(S\)。
如果中途没有区间可以选了，或者最后 \(|S|>cnt_x\)，就说明枚举的 \(x,cnt_x\) 不合法。
时间复杂度：设 \(V=\max(b_i)\)，那么最外层的二分是 \(O(\log V)\)，枚举 \(x,cnt_x\) 是 \(O(nV)\) 的，贪心过程是 \(O((n+m)\log n)\) 的。
显然过不了。
发现贪心过程优化不了了，只能优化枚举的部分。
钦定下文的 \(x\) 为 \(U\) 中 \(c_x\) 最大的。
性质二：存在一个最优的 \(S\)，满足 \(c_x\ge \max(c_i)-1\)。

证明：如果 \(c_x\le \max(c_i)-2\)，那么设 \(c_y=\max(c_i)\)。
所以 \(y \notin U\)，也就是说存在一个区间 \([l,r] \in S\)，但是他不包含 \(y\)。
如果我们选择不翻转 \([l,r]\) 那么 \(c_x\) 会 \(+1\)，\(c_y\) 会 \(-1\)，容易证明 \(y\) 此时仍然是 \(c_i\) 最大的 \(i\)。
这意味着我们把序列的最大值变小了，与 \(S\) 的最优性矛盾。
故原命题成立。

而注意到我们已经二分了 \(mid=\max(c_i)\)，所以 \(cnt_x\) 其实只有 \(b_x-mid\) 和 \(b_x-mid+1\) 两种选择。
这样枚举 \(cnt_x\) 就是 \(O(1)\) 的了。
性质三：存在一个最优的 \(S\)，满足 \(b_x=\max(b_i)\)。

证明：如果 \(b_x c_x=b_x-|S|\)，这就与 \(x\) 的定义矛盾了。
也就是说 \(S\) 中至少有一个区间不包含 \(y\)。
所以 \(b_x\le b_y-1,cnt_x-1\ge cnt_y\)。
浅浅推一下可以知道：\(b_x-2\times (cnt_x-1)\le b_y-1-2\times cnt_y\) 即 \(b_x-2\times cnt_x\le b_y-2\times cnt_y-3\) 即 \(b_x-cnt_x\le b_y+cnt_x-2\times cnt_y-3\)。
而 \(c_x=b_x-cnt_x\)，\(c_y=b_y+cnt_x-2\times cnt_y\)。
所以 \(c_x\le c_y-3\)，这与性质二矛盾了。
故原命题成立。

这样我们枚举的 \(x\) 的范围就缩小到 \(\{x|b_x=\max(b_i)\}\) 了。
性质四：存在一个最优的 \(S\)，满足 \(\{x|b_x=\max(b_i)\} \in U\)。

证明：如果有一个 \(y\) 满足 \(b_y=\max(b_i)\)，但是 \(y \notin U\)。
那么 \(b_x=b_y，cnt_x-1\ge cnt_y\)。
和性质三类似的可以知道此时有 \(c_x\le c_y-2\)，与性质二矛盾了。

所以任意一个 \(b_x=\max(b_i)\) 都是合法的，这样枚举 \(x\) 也变成 \(O(1)\) 的了。
所以这题的最终复杂度是 \(O((n+m)\log n\log V)\)。
code

代码不难写。我错是因为我太唐了

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！