Fluid Dynamics

翻譯題目敘述(強烈建議你看一下)

敘述

80000000 和 WlWl 是一對新手父母，得得百貨是一間任意商品均一價49元的百貨，這對夫妻在得得百貨買了一些神奇奶粉，每一種奶粉泡出來的牛奶都有各自的顏色和體積，他們發現當兩種牛奶放在一起時(一種在另一種之上)有時它們會交換位置！特別的，如果將體積為

$v_i$ 且顏色為

$c_i$ 的牛奶放在另一體積為

$v_j$ 且顏色為

$c_j$ 的牛奶之上，則會產生

$v_j\times c_j+(v_i+v_j)\times c_i$ 的位能，如果當兩種牛奶交換位置時位能變化

$\Delta \varphi$（定義為

${\varphi }_{new}-{\varphi }_{old}$） 大於等於

$W$（給定的值），則牛奶將會交換位置。否則不發生交換(注意: 牛奶不會混合，即使相鄰且顏色相同)。
現在，請寫一個程式模擬將牛奶加入杯子的過程

輸入

第一行將包含三個整數，

$N$

$Q$

$W$
接下來的

$N$ 行將包含兩個整數，

$v_i$ 和

$c_i$，每對對應於要放入的牛奶，將這些牛奶按照輸入的順序一一從杯子的頂部放入
接下來的

$Q$ 行查詢有兩種類型的查詢：

• INSERT v
  $c$ 表示從杯子頂部放置體積為
  $v$ 和顏色為
  $c$ 的牛奶
• K-TH k 表示輸出第
  $k$ 個牛奶（從罐子底部開始計數，從 1 開始）的體積和顏色

輸出

對每一個 K-TH 詢問輸出答案

範圍

$1\le N,Q\le 200000$

$1\le W\le {10}^{14}$

$1\le v_i,c_i\le {10}^9$
詢問保證合法

題解

Notice: 不管是

$O(\log N)$,

$O(log(N+Q))$ 還是log什麼的我都寫

$O(logN)$

首先一個 naive 的作法是維護 linked list，每次插入一個新的就一直往前直到不能為止，但是這樣是

$O((N+Q{)}^2)$。

你會發現瓶頸是因為要一直判斷可不可以往前，所以一個自然的想法就是分塊然後想辦法快速判斷可不可以直接跳過一整塊，然後(left as an exercise to the reader) 你會發現要判斷可不可以直接跳過一整塊可以對每一塊維護凸包就可以

$O(logN)$ 時間判斷! 假設每

$O(K)$ 個分一塊，那麼要花

$O((N+Q)logN/K)$ 的時間找到要掉哪一塊裡面，接下來就暴力在這塊內找要插在哪(

$O(K)$)並且重建這個凸包(

$O(K)$ 注意，重建凸包不能有 log，想一下要怎麼做)。

等等，這樣插入那塊大小不就+1了，要怎麼讓每塊大小是

$O(K)$，這時你看到 8w 在放閃於是你就靈光一閃: 如果一塊的大小+1完變成

$2K$，就暴力 split 成兩塊，最多split

$O(Q/K)$次，每次split花

$O(KlogN)$時間，這樣子，任何時刻每塊大小都是

$O(K)$ 了。

如果你仔細分析，總時間複雜度是

$O((N+Q{)}^{2}logN/K+(N+Q)K+QlogN)$ 然後 取

$K=\sqrt{(N+Q)logN}$ 複雜度會是

$O((N+Q)\sqrt{(N+Q)logN})$，有點卡常

Side note: 如果你程式裡寫const int K = 1000 其實你只是在做常數優化，因為複雜度還是平方的

#每日關心8w感情狀況
#每日關心8e7 fluid dynamics 進度
#每日關心wiwiho fluid dynamics 進度

感謝您閱讀這篇，最後附上 8e7 說他覺得很酷的鍵盤