二進位分組

不用cdq分治、平衡樹來實現斜率優化

二進位分組 | mgcht?

www.magichut.pw

一個想法

如果需要讓你維護一個數據結構

支持往裡面添加一個數據，或者查詢一個信息

且強制在線，應該怎麼做呢？

如果支持快速插入和快速查詢的話，直接做就好啦

下面從一道經典題目來探討

動態凸包

這裡有若干次操作，且強制在線，諸如
1. 添加一個點2. 給定x,y，從所有的點中找一個點(a,b)使得最大數據範圍

怎麼做？

設，現在要最大化z，整理一下式子： $-frac{x}{y}a+frac{z}{y}=b$

可以發現這個式子的意義是

經過點(a,b)，斜率為 $-frac{x}{y}$ ，截距為 $frac{z}{y}$ 的一條直線

現在需要最大化 $frac{z}{y}$ ，即最大化截距

斜率 $-frac{x}{y}<0$ ，即從上往下第一個碰到凸包上的點就會使得z最大

也就是要求維護動態凸包

平衡樹

由於只有加點，所以可以用平衡樹維護凸包上的點

插入時找到位置然後維護凸包

代碼量巨大，看起來不可寫

定期重構

有一個比較naive的方法

即每操作次就把所有的東西全部拿出來預處理

每次插入就新開一塊單獨處理

實現的話可以用vector套vector來實現

其中子vector維護的是凸包，父vector維護的是所有的凸包

查詢的話在每個凸包上查詢就好

時間複雜度

事實上定期重構的時間複雜度還是很差，這裡有一個更加優秀的做法

維個塊，大小分別（大概是這樣）為 $2^{log(n)},2^{log (n)-1},...$

這個用vector可以實現

每次添加點直接push_back

如果相鄰兩塊的大小相同，那麼將這兩塊合併掉，並彈掉最後一個塊

凸包合併的話，把所有的點都搞出來掃一遍就行（inplace_merge）

時間複雜度 $O(sumlimits_{i=1}^{log(n)}frac{n}{2^i} cdot 2^i cdot T(2^i))=O(n cdot log(n) cdot T(n))$

其中是處理大小為n的塊的時間

查詢的話在這個塊上二分就行

那麼問題來了

如果有刪除？

在統計貢獻和的時候可以通過新建一個有負貢獻的vector實現刪除

但是若要求查詢極值的話那就沒救了

既然是維護動態凸包

也就是說斜率優化可以用這個代替cdq分治或平衡樹

雖然時間複雜度多一個log，但還算是較為優秀（好寫）

嘗試用二進位分組實現某些數據結構

堆

實現一種數據結構，支持三種操作

1. 將一個值插入到數據結構
2. 查詢最小值3. 將最小值刪除（如果有多個，只刪除一個）

每個塊可以用一個遞減的vector來實現，這樣合併只需要inplace_merge

時間複雜度

如果用雙端隊列來實現內層的vector，可以實現雙端堆

平衡樹

實現一種數據結構，支持三種操作
1. 插入一個值2. 刪除一個值3. 查詢某個值的排名4. 查詢排名為k的值

5. 查詢某個值的前驅
6. 查詢某個值的後繼

由於操作比較多，在此分開討論

對於每一個子vector，依舊是維護有序的形式

插入

直接扔進vector里，然後維護二進位分組的性質

刪除

再開一個vector，表示刪除的元素

刪除一個元素相當於在這個新開的vector中加入並維護二進位分組

查詢排名

在所有表示插入的vector中二分排名，並減去表示刪除的vector中的貢獻 $egin{align*} &O(log(n) cdot sum_{i=1}^{log(n)}log(2^i))\ &= O(log(n) cdot log(Pi_{i=1}^{log(n)}2^i)) \ &= O(log(n) cdot log(2^{sum_{i=1}^{log(n)}i})) \ &= O(log(n) cdot frac{(1+log(n)) cdot log(n)}{2})\ &= O(log^2(n)) end{align*}$

查詢kth

二分答案後查詢排名

前驅

結合查詢排名和查詢kth解決

後繼

結合查詢排名和查詢kth解決

一些練習題

bzoj 2989
bzoj 4170
bzoj 4140
bzoj 1190
bzoj 1492
bzoj 3963
codeforces 710 F
luogu P3378
luogu P3369

二進位分組

一個想法

動態凸包

平衡樹

定期重構