CDQ 分治與整體二分

CDQ 分治

主要是一種分治思想，常用于解決偏序問題。

例如三維偏序問題，我們采用的方法是先處理以第一關鍵字為區分的左區間、右區間內的答案，再處理左右區間互不干涉的答案。

四維偏序呢？

咕咕咕

整體二分

主要內容

如果題目問我們第 \(k\) 大、最小的最大、最大的最小等問題，我們通常使用二分來解決。

但是如果有多組詢問，每次詢問都需要使用二分，就會變得非常慢~，所以有了整體二分。

整體二分通常用于解決多組詢問的類二分問題，與二分類似，都是通過猜測答案所屬區間來得到答案的。

舉個例子：如果出題人告訴我們，所有測試點的答案都是在 \([0,10^9]\) 間的整數，每輸出一個答案測試點都會返回這個答案比答案小還是大。我們就不用對于每個測試點去二分答案了，可以二分一次，將答案小于它的拿在左手，大于它的拿在右手，這樣就快很多了。

實際操作中，我們常用 solve(ql,qr,al,ar) 表示現在剩余的詢問編號為 \([ql,qr]\)，猜測的答案區間在 \([al,ar]\) 之間，每次將 \([al,amid]\) 內的貢獻加入從而判斷剩余詢問的答案分別屬于哪個范圍。

例題

整體二分題單

總結

以上是生活随笔為你收集整理的CDQ 分治与整体二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。