一个想法
如果需要让你维护一个数据结构
支持往里面添加一个数据，或者查询一个信息
且强制在线，应该怎么做呢？
如果支持快速插入和快速查询的话，直接做就好啦
下面从一道经典题目来探讨
动态凸包
这里有若干次操作，诸如
- 添加一个点
- 给定$x,y$，从所有的点中找一个点$(a,b)$，使得$a \cdot x+b \cdot y$最大
强制在线，且数据范围如下
$1 \le a,b,x,y \le 10^9$
$1 \le n \le 50000$
怎么做？
设$z=ax+by$，现在要最大化$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的方法
即每操作$\sqrt n$次就把所有的东西全部拿出来预处理
每次插入就新开一块单独处理
实现的话可以用vector套vector来实现
其中子vector维护的是凸包，父vector维护的是所有的凸包
查询的话在每个凸包上查询就好
时间复杂度$O(n \cdot (\sqrt n + \log n))=O(n \cdot \sqrt n)$
二进制分组
事实上定期重构的时间复杂度还是很差，这里有一个更加优秀的做法
维护$\log n$个块，大小分别（大概是这样）为$2^{\log(n)},2^{\log (n)-1},…$
这个用vector可以实现
每次添加点直接push_back
如果相邻两块的大小相同，那么将这两块合并掉，并弹掉最后一个块
凸包合并的话，把所有的点都搞出来扫一遍就行（inplace_merge）
时间复杂度$O(\sum\limits_{i=1}^{\log(n)}\frac{n}{2^i} \cdot 2^i \cdot T(2^i))=O(n \cdot \log(n) \cdot T(n))$
其中$n \cdot T(n)$是处理大小为$n$的块的时间
查询的话在这$\log(n)$个块上二分就行
那么问题来了……
如果有删除？
在统计贡献和的时候可以通过新建一个有负贡献的vector实现删除
但是若要求查询极值的话那就没救了
既然是维护动态凸包
也就是说斜率优化可以用这个代替cdq分治或平衡树
虽然时间复杂度多一个log，但还算是较为优秀（好写）
尝试用二进制分组实现某些数据结构
堆
实现一种数据结构，支持三种操作
- 将一个值插入到数据结构
- 查询最小值
- 将最小值删除（如果有多个，只删除一个）
每个块可以用一个递减的vector来实现，这样合并只需要inplace_merge
时间复杂度$O(n \cdot \log(n))$
如果用双端队列来实现内层的vector，可以实现双端堆
平衡树
实现一种数据结构，支持三种操作
- 插入一个值
- 删除一个值
- 查询某个值的排名
- 查询排名为$k$的值
- 查询某个值的前驱
- 查询某个值的后继
由于操作比较多，在此分开讨论
对于每一个子vector，依旧是维护有序的形式
插入
直接扔进vector里，然后维护二进制分组的性质
$$
O(\log(n))
$$
删除
再开一个vector，表示删除的元素
删除一个元素相当于在这个新开的vector中加入并维护二进制分组
$$
O(\log(n))
$$
查询排名
在所有表示插入的vector中二分排名，并减去表示删除的vector中的贡献
$$
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))
$$
查询kth
二分答案后查询排名
$$
O(\log^3(n))
$$
前驱
结合查询排名和查询kth解决
$$
O(\log^3(n))
$$
后继
结合查询排名和查询kth解决
$$
O(\log^3(n))
$$
一些练习题
- bzoj 2989
- bzoj 4170
- bzoj 4140
- bzoj 1190
- bzoj 1492
- bzoj 3963
- codeforces 710 F
- luogu P3378
- luogu P3369
