整體二分（二分進階）

前言：

Claris表示：這東西考試的時候估計是用不上的，現在很多題目，尤其是進階資料結構題都會強制線上

但是今天挖的坑，不知道什麼時候就會掉進去。。。早填早安心

知識儲備

二分答案——整體二分的前世

首先對于一類查詢而言，我們要找的答案滿足二分性：

例如：區間第K大

這時候我們就可以采用二分答案的方法來解決，二分答案是把九三問題轉化為判定問題的有效手段

二分答案的做法是不斷維護一個可能的答案區間[L,R]，每次二分，我們先求出目前的判定答案

M=(L+R)>>1，然後我們統計在目前标準下會對查詢産生貢獻的修改（例如參數<=M）的貢獻和，

我們再比較現在的貢獻和與我們想要的貢獻和的大小，如果貢獻已經超過我們想要的貢獻和，說明符合标準的修改太多了，我們需要縮緊标準 —>[L,M]

否則我們就要放寬标準 —>[M+1,R]

算法介紹

整體二分，就像題目說的那樣：是樸素二分的進階版

整體思路有一點像CDQ分治

看一下《淺談資料結構題的幾個非經典解法》中的介紹：

所謂整體二分，需要資料結構題滿足以下性質：

1. 詢問的答案具有可二分性

2. 修改對判定答案的貢獻相對獨立，修改之間互不影響效果

3. 修改如果對判定答案有貢獻，則貢獻為一确定的與判定标準無關的值

4. 貢獻滿足交換律，結合律，具有可加性

5. 題目允許離線操作

詢問的答案有可二分性質顯然是前提，我們發現，因為修改對判定标準的貢獻相對獨立，且貢獻的值（如果有的話）與判定标準無關，是以如果我們已經計算過某一些修改對詢問的貢獻，那麼這個貢獻永遠不會改變，我們沒有必要當判定标準改變時再次計算這部分修改的貢獻，隻要記錄下目前的總貢獻，再進一步二分時，直接加上新的貢獻即可

這樣的話，我們發現，處理的複雜度可以不再與序列總長度直接相關了，而可能隻與目前待處理序列的長度相關

我仔細一琢磨，這不就是CDQ嘛。。。

實際上說不同也是有不同的（不同點還不少）

具體流程

我們先看一道例題：帶修改區間第k小數

一看，哎呦，這不是主席樹嘛？

但是我們就是要沒事找事

對于單個查詢而言，我們可以采用預處理+二分答案的方法解決，但現在我們要回答的是一系列的查詢，對于查詢而言我們都要重新預處理然後二分，時間複雜度無法承受，但是我們仍然希望通過二分答案的思想來解決，整體二分就是基于這樣一種想法——我們将所有操作（包括修改和查詢）一起二分，進行分治

整體二分具體做法比較難了解，看一下僞代碼：

Divede(Q,L,R)
//Q是目前處理的操作序列 
//WANT是要求的貢獻,CNT為已經累計的貢獻(記錄的是1~L-1所有修改的貢獻) 
//[L,R]是詢問的答案範圍區間
if L=R then
    将Q中所有是詢問操作的答案設為L
end if 
//我們二分答案,M是目前的判定答案
M=(L+R)>>
//solve是主處理函數,隻考慮參數滿足判定标準[L,R]的修改的貢獻,
//因為CNT域中已經記錄了[1,L-1]的修改的貢獻了,這一步是保證時間複雜度的關鍵,
//solve隻與目前Q的長度有關,而不與整個操作序列的長度有線性關系 
solve(Q,L,M);
//solve之後Q中各個參數滿足判定标準的修改對詢問的貢獻被儲存在ANS數組 
//Q1,Q2為了兩個臨時數組,由于劃分操作序列
for i= to Length(Q) do
    if (Q[i].WANT<=Q[i].CNT+ANS[i]) then
        //目前已有貢獻不小于要求貢獻，說明最終答案應當不大于判定答案 
        向數組Q1末尾添加Q[i] 
    else
        //目前已有貢獻小于要求貢獻,說明最終答案應當大于判定答案 
        //這裡是整體二分的關鍵,把目前貢獻累計入總貢獻,以後不再重複統計 
        Q[i].CNT=Q[i].CNT+ANS[i]
        向數組Q2末尾添加Q[i]
    end if
end for
//分治,遞歸處理 
Divide(Q1,L,M)
Divede(Q2,M+,R) 
           

我們時刻維護一個操作序列和對應的可能答案區間[L,R]

我們先求的一個判定答案M=（L+R）>>1

然後我們考慮操作序列的修改操作，将其中符合條件（例如參數<=M）的修改對各個詢問的貢獻統計出來

然後我們對操作序列進行劃分

• 第一類操作是查詢

  • 如果目前累計貢獻比要求貢獻大，說明M過大，滿足标準的修改過多，我們需要給這個查詢設定更小的答案區間，于是把ta劃分到答案區間[L,M]

    （這種情況下我們不改變查詢的CNT域，保證了繼續下一次分治時這些查詢的CNT還是累計[1,L-1]的修改的貢獻）

  • 否則我們将目前已經統計到的貢獻更新，将ta劃分到[M+1,R]

    （這種情況下我們将[L,M]内的修改的貢獻更新了CNT域，保證了下次繼續分治時這些查詢的CNT域已經保留的是[1，M]的貢獻了）

• 第二類操作是修改

  假如ta符合目前的标準，已經被統計入了貢獻，那麼ta對于答案區間是[M+1，R]的查詢來說已經沒有意義

  （因為我們知道ta一定會對這些查詢産生貢獻，并且我們已經累計了這種貢獻到CNT域中），我們就把ta劃分到[L,R]的區間裡

  對于不符合目前的标準，未被統計入貢獻的修改來說，如果我們放寬标準，ta有可能起貢獻，然而我們并未統計這種貢獻，是以對于[M+1,R]的區間來說它仍具有考慮的意義，我們把它劃分到[M+1,R]中

劃分好了操作之後，我們就可以繼續二分下去了

時間複雜度

和CDQ分治一樣，整體二分的複雜度也是O(f(n)logn)

說了這麼多，還是看例題：poj2104 K-th Number

題解