十年 OI 一場空，不開 long long 見祖宗。

一個(gè) long long 調(diào)了我半個(gè)小時(shí)……

思路很好想，線段樹上二分。怎么想出來的呢？眾所周知，水銀? 和水? 是不互溶的，而且水銀的密度遠(yuǎn)大于水，所以水會漂在水銀的上方?，F(xiàn)在我們要讓加水的試管的最大高度盡可能小，從這里可以推導(dǎo)出一個(gè)非常顯而易見的結(jié)論：

最優(yōu)方案中最后所有有水的試管的液面高度一定是相同的，否則不是最優(yōu)方案。

可以用反證法證明：

若此情況不是最有情況，則一定有另外一種情況比這種情況更優(yōu)。

假設(shè)最優(yōu)情況中最低試管的液面高度為?，最高試管的液面高度是?，且?。

我們不妨設(shè)?。那么我們可以把最高試管中的水倒一點(diǎn)到最低試管中，使得 變小，由此得到一個(gè)更優(yōu)的情況。此結(jié)論與此情況是最優(yōu)情況的假設(shè)矛盾。故結(jié)論得證。

接著，我們看到這個(gè)題目的表述非常像二分啊。（那就試試）

它有沒有單調(diào)性呢？顯然有的。

上二分！然后用權(quán)值線段樹維護(hù)一下就沒了……

Code: