切符の手配 (Arranging Tickets))

記錄一下這道推性質(zhì)神題。其實是因為這題給我調(diào)紅溫了，反復(fù)看錯題意+小錯誤一大堆。

題意

這個題意太難看懂了，放個形式化題意：
有 \(m\) 種區(qū)間，第 \(i\) 種區(qū)間 \([a_i,b_i]\) 有 \(c_i\) 個。
維護(hù)一個初始全為 \(0\) 的序列 \(a\)，對于每個區(qū)間 \([l_i,r_i]\)，有兩種選擇：

1. 把 \([l_i,r_i]\) 中的數(shù) \(+1\)。
2. 把 \([1,l_i)\cup(r_i,n]\) 中的數(shù) \(+1\)。

請最小化最終 \(a_i\) 的最大值。

題解

首先二分，接下來只需要 check 答案是否可以為 \(mid\)。
我們先讓所有區(qū)間都選擇第 \(1\) 種操作，令 \(b_i\) 表示此時的 \(a_i\)；\(c_i\) 表示最優(yōu)方案下的 \(a_i\)。
我們可以將某些區(qū)間的操作變?yōu)椴僮?\(2\)（我們稱為翻轉(zhuǎn)操作），設(shè)為集合 \(S\)。
\(S\) 為空的情況直接判一下即可，下面默認(rèn) \(S\) 不為空。

性質(zhì)一：存在一個最優(yōu)的 \(S\)，滿足集合 \(S\) 中的區(qū)間的交一定不為空。

證明：反證法，如果結(jié)論不成立，那么 \(S\) 中必然存在某兩個區(qū)間 \(A,B\) 不相交。
相比于不翻轉(zhuǎn) \(A,B\)，看一些 \(a\) 序列中的 \(a_i\) 有什么變化：
(1) \(i \in A \cup B\)：不變。
(2) \(i \notin A \cup B\)：\(+2\)。
所以翻轉(zhuǎn)他倆沒有任何元素的值會變小，所以肯定不優(yōu)。

下面我們設(shè)區(qū)間 \(U\) 表示 \(S\) 中這些區(qū)間的交。
設(shè) \(cnt_i\) 表示位置 \(i\) 被 \(S\) 中的區(qū)間覆蓋的次數(shù)。
我們可以枚舉 \(U\) 中的某個位置 \(x\)，然后去枚舉 \(cnt_x\)，由性質(zhì)一可知 \(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\)。
我們可以根據(jù)這個下界去貪心地確定集合 \(S\)，具體地，我們從小到大掃描 \(i\)（\(i\ne x\)）：
如果 \(cnt_i\) 還沒有抵達(dá)下界，那么就在所有還沒選過的包含 \(i\) 且包含 \(x\) 的區(qū)間中選一個右端點最大的區(qū)間加入 \(S\)。
如果中途沒有區(qū)間可以選了，或者最后 \(|S|>cnt_x\)，就說明枚舉的 \(x,cnt_x\) 不合法。

時間復(fù)雜度：設(shè) \(V=\max(b_i)\)，那么最外層的二分是 \(O(\log V)\)，枚舉 \(x,cnt_x\) 是 \(O(nV)\) 的，貪心過程是 \(O((n+m)\log n)\) 的。
顯然過不了。

發(fā)現(xiàn)貪心過程優(yōu)化不了了，只能優(yōu)化枚舉的部分。
欽定下文的 \(x\) 為 \(U\) 中 \(c_x\) 最大的。

性質(zhì)二：存在一個最優(yōu)的 \(S\)，滿足 \(c_x\ge \max(c_i)-1\)。

證明：如果 \(c_x\le \max(c_i)-2\)，那么設(shè) \(c_y=\max(c_i)\)。
所以 \(y \notin U\)，也就是說存在一個區(qū)間 \([l,r] \in S\)，但是他不包含 \(y\)。
如果我們選擇不翻轉(zhuǎn) \([l,r]\) 那么 \(c_x\) 會 \(+1\)，\(c_y\) 會 \(-1\)，容易證明 \(y\) 此時仍然是 \(c_i\) 最大的 \(i\)。
這意味著我們把序列的最大值變小了，與 \(S\) 的最優(yōu)性矛盾。
故原命題成立。

而注意到我們已經(jīng)二分了 \(mid=\max(c_i)\)，所以 \(cnt_x\) 其實只有 \(b_x-mid\) 和 \(b_x-mid+1\) 兩種選擇。
這樣枚舉 \(cnt_x\) 就是 \(O(1)\) 的了。

性質(zhì)三：存在一個最優(yōu)的 \(S\)，滿足 \(b_x=\max(b_i)\)。

證明：如果 \(b_x<\max(b_i)\)，設(shè) \(b_y=\max(b_i)\)。
那顯然 \(y \notin U\)，因為如果 \(y \in U\)，則 \(c_y=b_y-|S| > c_x=b_x-|S|\)，這就與 \(x\) 的定義矛盾了。
也就是說 \(S\) 中至少有一個區(qū)間不包含 \(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\)，這與性質(zhì)二矛盾了。
故原命題成立。

這樣我們枚舉的 \(x\) 的范圍就縮小到 \(\{x|b_x=\max(b_i)\}\) 了。

性質(zhì)四：存在一個最優(yōu)的 \(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\)。
和性質(zhì)三類似的可以知道此時有 \(c_x\le c_y-2\)，與性質(zhì)二矛盾了。

所以任意一個 \(b_x=\max(b_i)\) 都是合法的，這樣枚舉 \(x\) 也變成 \(O(1)\) 的了。

所以這題的最終復(fù)雜度是 \(O((n+m)\log n\log V)\)。

code

代碼不難寫。我錯是因為我太唐了