《浅谈数据结构题的几个非经典解法》学习笔记

按照时间分治和二进制分组

参考：《浅谈数据结构题的几个非经典解法》--许昊然

按照时间分治

在一些数据结构题目中，如果满足以下性质：

修改操作彼此独立，且互相不会产生影响

可以离线

那么我们就可以用按照时间分治，把操作分为两部分，很显然右边的操作不会对左边产生影响，那么左边直接递归即可。

而右边只会受到两个影响：左边所有的操作造成的影响以及右边的操作造成的影响。由于修改彼此独立，且不会互相影响，所以这两部分可以分开计算。右边的操作造成的影响是与左边无关的，所以也可以递归处理。而左边的操作对右边的操作影响是一定的，所以问题就被转化为

一开始给定一些操作，然后离线回答若干询问。

假设这一部分时间复杂度为(f(n))，那么总的时间复杂度即为：

[T(n)=2T(n/2)+O(f(n))le O(f(n)log n) ]

例题：

共点圆：

有一个平面，需要维护以下操作：

插入一个圆心为((x,y))且过原点的圆。

给定一个圆((x_0,y_0))，询问其是否在所有的圆中(包括边界)。

std: 对圆进行反演后，转化为凸包维护问题，用splay动态维护凸包，支持插入新点和查询点是否在凸包内部，时间复杂度为(O(nlog n))

使用上面的方法：

首先对于时间进行分治，考虑左边对右边的贡献：

一个点((x_0,y_0))是否在以((x,y))为圆心且过原点的圆内可以转化为：

[egin{matrix} (x-x_0)^2+(y-y_0)^2&le &x^2+y^2\ x_0^2 +y_0^2 &le &2xcdot x_0+2ycdot y_0 end{matrix} ]

那么问题就可以被转化为给定一些点，每次询问一个半平面，查询所有的点是否都在半平面上，这个可以维护凸包在(O(nlog n))求解，总时间复杂度为(O(n log^2n))。

但是这个可以进行优化，因为这是一个分治算法，那么我们在求的时候已经求出来了左边和右边的凸包和斜率，那么我们就可以(O(n))的时间复杂度进行处理，总时间复杂度为(O(nlog n))，然而这个做法常数和代码复杂度都比较高。

按照二进制分组

但是有一些数据结构题，满足修改互相独立，但不支持离线算法，这时候按时间分治就已经失去了作用。

但是我们可以用二进制分块进行处理。考虑一个数的二进制位，如果我们把他分为二进制位块，如：

(21=16+4+1),则将其分为16,4,1三块，分别统计答案。

(22=16+4+2),则将其分为16,4,2三块。

这样，我们将操作进行了分块，并且在每一块里用数据结构进行维护，在查询时由于询问互不影响，可以直接在每一块内进行并合并。

而当新加入修改时，对于后面不再存在的几块直接删除，然后暴力合并即可。

假设在每一块中询问时间复杂度为(O(g(n)))，合并修改的时间复杂度为(O(f(n)))。

我们分析一下这个做法的复杂度，加入修改时，设加入后修改的总数为k，那么合并的时间复杂度就是(O(f(lowbit(k))))。

合并总时间复杂度即为：

[egin{matrix} T(n)&=&sum_{k=0}^nf(lowbit(k))& \ &=&sum_{k=1}^{log n}frac{n}{2^{i+1}}f(2^i)& \ &le&sum_{k=1}^{log n}O(f(n))&=O(f(n)log n) end{matrix} ]

而查询复杂度很显然就是(O(ncdot g(n)log n))

所以总时间复杂度即为(O(f(n)log n+ncdot g(n)log n))

例题：

给定一个平面，要求在线进行以下操作：

插入一个半平面

查询一个点是否被所有的半平面包含

那么直接维护每一个集合的半平面交，如果集合大小为k，那么时间复杂度即为(O(klog k))。查询时将半平面交上的点按照极角排序，对于一个点可以二分出所在的三角形，即可完成(O(log n))回答每次询问，总时间复杂度即为(O(nlog^2n))。

而我们如果不用二进制分块而采用其他的进制，时间复杂度略有不同，有时则可以达到更优的复杂度。

有一类题目允许使用离线算法，修改操作包括插入和删除，其中虽然插入操作相互独立，但是修改操作会对插入造成影响，这样我们就无法直接套用原来的方法。

例题：

给定一个平面，要求进行以下操作：

插入一个半平面

删除一个半平面

查询一个点是否被所有的半平面包含

我们仍然按照前面的分治思路，考虑后面的答案只会与下面两个有关：

前一半所有插入操作到询问时还未被删除的操作

后一半所有插入操作到询问时还未被删除的操作

因为后一半的操作一定不会在前一半被删除，这个直接递归即可。

而前一半的插入操作在前一半中还没有被删除的操作则会对后面产生贡献，那么问题变成了：

删除一个半平面

查询一个点是否被所有的半平面包含

考虑这个东西还是不好搞，如果是插入就好了。

如果是插入就好了

因为这是一个离线的算法，所以我们可以提前知道最后还有哪几个操作还没有被删除，那么我们把时间翻转一下，就可以变成插入了，这个问题在上面已经解决了,可以使用(O(nlog^2n))的算法求解。

那么总时间复杂度就是(O(nlog^3n))。

如果使用时间分治里面的那一套方法的话，时间复杂度即可达到(O(nlog^2n))，常数和代码复杂度都要比标程的线段树套可持久化平衡树要优秀。

~~但是不能在线啊，因为里面有时间翻转操作。~~

整体二分

二分答案是一个常用的技巧，但是二分答案时所有的答案都有可能被访问到，这就要求进行预处理，而这个有时是无法忍受的，这个时候就可以进行整体二分。

条件

进行整体二分需要满足以下条件：

询问的答案具有可二分性。

修改对判定答案的贡献独立，修改之间互不影响效果。

修改如对判定答案有贡献，则贡献为一确定的与判定标准无关的值。

贡献满足交换律，结合律，具有可加性。

题目允许离线算法。

对于第一条其意义显然。

因为修改对判定答案的贡献独立，且修改之间互不影响，所以如果我们已经计算过一些修改对询问的贡献，那这个贡献永远不会改变，而且不会因为判定标准的改变而重新计算。

这样的话，我们可以发现，处理的时间复杂度不再与序列的长度有关，而与询问的长度有关。

设询问序列的长度为S，待二分的序列长度为C，单次处理的复杂度为(f(n))，那么时间复杂度可以表示为：

[T(C,S)=T(frac{C}{2},S_0)+T(frac{C}{2},S-S_0)+f(S)le O(f(S)log C) ]

例题

一道例题

给定一个序列，查询一个区间中的第k大值。

当然可以主席树/划分树了。
考虑使用整体二分。设目前二分出的值为s，那么对于一个询问((l,r,k))判断在区间((l,r))上大于等于s的数的个数，如果这个值小于k，那么就把这个询问放到右边进行处理；如果这个值大于k，那么大于s的数的贡献是不会变的，那么直接把k减去s然后放到左边进行处理。现在需要考虑的就是如何求出在一个区间内大于等于s的数的个数。
如果我们开一个数组，在大于等于s的数的位置设成1，否则设成0，然后做一个前缀和，那这个复杂度为

[T(C,S)=T(frac{C}{2},S_0)+T(frac{C}{2},S-S_0)+O(n)=O(Cn) ]

这个复杂度与暴力无异，那么我们看看这个做法哪里错了。
在整体二分时，进行信息统计只能与处理的区间有关，不能与整体的序列有关。此题可以把大于s的数的编号拿出来排序，每个区间直接在上面进行二分即可，时间复杂度即为(O((n+Q)log nlog C))

矩阵乘法

给定一个矩阵，要求查询一些子矩阵的第k大值。

考虑整体二分，借助上一题的思路，原问题变成了：

给定一个矩阵，上面的某些值被标记了，要求回答一系列询问：
    查询某个子矩阵中被标记的值的个数。
    额外要求：复杂度不允许与矩阵大小线性相关，只能与被标记元素个数相关。

这个问题可以用二维树状数组解决。这里清空树状数组时不能简单地清空，而要把修改过的值清空，这样才能做到只与被标记元素个数相关。

时间复杂度为(O((n^2Q)log^2nlog C))

ZJOI2013 K大数查询

有n个数集（可以有重复元素），要求支持：

在第l个数集到第r个数集中插入数(k(1le kle n))
询问如果把第l个数集到第r个数集的数取出来放到一起，那么其中的第k大数是什么

我当然知道可以树套树。

考虑用整体二分，原问题变成了

有一个序列，要求支持：

对该序列区间加1

询问区间和
额外要求：复杂度不允许与序列长度线性相关，只能与操作个数相关。

我当然知道可以动态开点线段树。

考虑按时间分治，原问题变为：

开始时给出若干区间，要求回答若干查询：

给定一个区间，求出开始时给定的区间与该区间的交集之和。

显然可以排序后扫一下，时间复杂度为(O(nlog^3n))

如果用归并排序，时间复杂度为(O(nlog^2n))

小结

整体二分是一种很有效的处理手段，能大幅简化许多题目，如把前面的例题加强一下：

给定一个平面，要求进行以下操作：

插入一个带权半平面

删除一个半平面

查询包含了某个点的权值最大的半平面

这个题目如果不用整体二分就难以解决，如果使用了整体二分，这个题目就可以化成上面的例题的形式，就可以套用上面的算法在(O(nlog^3n))时间复杂度内解决。