一个想法

如果需要让你维护一个数据结构

支持往里面添加一个数据,或者查询一个信息

且强制在线,应该怎么做呢?

如果支持快速插入和快速查询的话,直接做就好啦

下面从一道经典题目来探讨

动态凸包

这里有若干次操作,诸如

  1. 添加一个点
  2. 给定$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,但还算是较为优秀(好写)

尝试用二进制分组实现某些数据结构

实现一种数据结构,支持三种操作

  1. 将一个值插入到数据结构
  2. 查询最小值
  3. 将最小值删除(如果有多个,只删除一个)

每个块可以用一个递减的vector来实现,这样合并只需要inplace_merge

时间复杂度$O(n \cdot \log(n))$

如果用双端队列来实现内层的vector,可以实现双端堆

平衡树

实现一种数据结构,支持三种操作

  1. 插入一个值
  2. 删除一个值
  3. 查询某个值的排名
  4. 查询排名为$k$的值
  5. 查询某个值的前驱
  6. 查询某个值的后继

由于操作比较多,在此分开讨论

对于每一个子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