【听课笔记】离线分治选整

主要是一些听dls讲课的笔记。感觉好神仙啊,这我怎么可能会。

Part1 神奇的暴力

bitset做 $K$ 维数点

令 $f(k,w)=\{i|x_{i,k}< w\}$.

即第 $k$ 维小于 $w$ 的集合。

然后查询的话,对于第 $p$ 个点,就求一下

这东西即可。

预处理的话,考虑先 $O(Kn)$ 让每个 $x_{i,k}$ 都赋值到 $f_{k,x_{i,k}+1}$ 上,然后从头到尾 $or$ 下来,就变成了 $K\frac{n^2}{w}$ 的复杂度。查询复杂度就是 $O(K\frac{n}{w})$ 。

思考空间复杂度,大概是 $O(K\frac{n^2}{w})$ 。发现似乎有点卡空间。于是考虑设置一个阈值 $T$,换设一个 $f_{k,iT}$ 用来只记录 $T$ 的倍数的情况,这样空间复杂度就会降为 $\frac{Kn^2}{Tw}$ ;查询的时候就可以查询离 $x_{p,i}$ 最近的块,然后把后面的下脚料暴力加进去,时间复杂度变成了 $O(Kn(\frac{n}{w}+T))$ 。

Part2 CDQ分治

动态凸壳

给出一个平面,支持加点 $(x,y)$ ,给出 $(a,b)$ 查询最大的 $ax+by$ 。

发现本质上是在求某个方向上最大的点积,本质上就是在动态维护凸壳。于是有两种做法:

(1)直接 set<point> 维护,支持按 $x$ 查询和按斜率查询。插入的时候按 $x$ 排序,询问按斜率排序。可以在 cmp 里记用个全局变量来判断当前按什么排序(神奇的是这样复杂度是对的)。反正就是维护凸壳就对了。

这个地方很迷的就是,如果每次查询的是 $kx+y$ 这种形式,那么斜率可以下取整。

(2)CDQ分治,变成了静态维护凸包。发现两边都排完序之后,中间就可以直接大力归并了,所以是可以做到 $n\log n$ 的。

CF 848C

给⼀个数列,定义⼀段的权值为每个不同的数值最后⼀次出现的位置减去第⼀次出现的位置和。

要求单点修改/求某⼀段的权值和。

神仙找性质题。考虑令每个 $i$ 的贡献是 $i-\mathrm{pre}_{a_i}$,那么就是在二维数点: $\sum_{l \leq \text { pre}_{a_{i}}<i\leq r} i-\text {pre}_{a_i}$ 。于是可以直接CDQ分治。

UOJ#50 链式反应

求解微分方程

的前 $m$ 项。

化一下式子

然后考虑大概是一个分治FFT形式。于是考虑CDQ分治。然后考虑怎么看左边系数对右边的贡献。

考虑如果 $l=0$ 。那么本质上就是 $f_{0\sim mid}^2* p_{0\sim r-1}$ 然后把 $>mid$ 的那些贡献全部累加。

否则一定有 $2\cdot l>r$ 。发现 $i\in [l,mid]$ 或 $j\in [l,mid]$ ,对于任意 $i\in [l,mid]$,均有 $r-1-i<l$ 。所以最后就变成了 $f_{0\sim r-1-l},p_{0\sim r-1-l}$ 和 $f_{l\sim mid}$ 的卷积。

复杂度 $m\log ^2 m$ 。

Part3 线段树分治

动态图连通性

回溯的时候仍然需要删除某些边,但是发现删边的顺序等于加边的顺序的倒序。即,我们将无序的删除转化为了操作栈的压入和弹出。此时只需维护一个可回退并查集即可。注意此处的并查集需要按秩合并,因为路径压缩的复杂度是均摊的,无法保证回退时的复杂度。

不包含某个物品的背包

普通的背包加入是 $O(m)$,合并是 $O(m^2)$,删除是 $O(nm)$ 的。

考虑线段树分治。一个物品的存活时间是 $[1,k-1]$ 和 $[k+1,n]$ 。令 solve(l,r,f) 表示把 $[l,r]$ 之外的物品加入背包时得到的是 $f$ 。于是就考虑分治下去,对于 solve(l,mid,g) 而言,gf 和 $mid+1\sim r$ 之间信息的合并;反之 solve(mid + 1,r,h)h 需要时 f 和 $l\sim mid$ 的信息的合并。分治下去即可。

最终复杂度 $O(nm\log n)$ .

不经过某个点的最短路/方案数

跟上个题本质一样? 直接做显然是 $n^4$ 的嘛,所以就线段树分治一下就好了。

HNOI城市建设

支持修改边权和查询MST。

还是考虑线段树分治嘛,但是 LCT 做就显然复杂度不是那么靠谱。

考虑一种不用 LCT 的做法。发现假设要修改 $1$ 条边,那么这个修改至多会影响一条边,也就是对于 solve(l,r) 最多会影响 $O(r-l)$ 条边。发现这个变化量并不大,正好满足分治的复杂度。于是考虑图和把每一层的操作数都降到 $O(r-l)$ 。

考虑对于不在当前区间的边集的边进行分类,一类是一定不会在MST中的,一类是一定会在MST中的。具体的,对于分治的每一层,设当前层需要修改的边集为 $E$,那么首先把 $E$ 中的边权均设为 $-\infty$ 跑一次MST,这样MST中 $\not \in E$ 以外的边就是必选边;再设为 $+\infty$ ,这样MST中 $\not \in E$ 的就是必不选边。

注意到,如果每次将必选边连成的连通块缩起来,这样分治下去每层的点数就是 $O(r-l)$ 的;如果每次将所有必不选边删掉,那么由于至多是生成树上那些边,跟点数同阶,也是 $O(r-l)$ 的,再加上本层的 $O(r-l)$ 的边,最终边集也是 $O(r-l)$ 的。这样复杂度就对了。最终复杂度为 $n\log^2 n$ ,其中另一个 $\log$ 是可回退并查集的。

改天写一下这题吧quq

嫖来的笔记

山东队长swk写的吼哇!

UOJ#191 Unknown

维护向量序列,支持末尾插入/删除元素,询问区间与输入的向量点积最大值。

发现只有末尾插入和区间查询的话大概可以 2048 着做。这个 2048 大概是指每插入一个元素,都合并到最小的那一堆里,然后将这一堆二进制拆分,如果合并后存在和他一样大小的一堆就继续合并。查询的时候就每一堆分别查询,总查询复杂度会多一个 $\log $。从这个地方也可看出,由于只需要重构,所以不需要插入删除十分优秀。

考虑重构复杂度。重构的复杂度分析时大多都是均摊分析:每个元素最多被重构 $\log n$ 次,所以最多是 $n\log n$ 的。

由于线段树的合并操作有着较优的复杂度,于是考虑用线段树来维护。这样大概是 $O(n\log^2 n)$ 的复杂度。

接下来考虑带删除操作的问题。

如果是离线,由于只有末尾的插入和删除,可以用版本树的思想来做,大概是随着序列递增,建出一棵深度递增的树,对于 $i$ 号结点后面的 Ins, Del , Ins, Ins , Del, Del, Ins 而言,代表着该结点的三个分支(儿子),然后每次算大概就是树剖一下,这样就是 $\log ^ 3n$ 的复杂度了:线段树里面两个 $\log $,凸包二分再要一个 $\log$ 。(这个地方复杂度还是不很会算,好像是如果将询问排序就可以少一个 $\log$ 所以最后是 $3$ 个 $\log$,好像很nb的样子)。

考虑在线如何用二进制分组来做。如果直接暴力做,就不能保证每个元素都被合并 $\log n$ 次,所以在某个块末尾反复插入删除就会人没了。

于是考虑两种方法解决这个问题。

第一种是类似 $\rm Treap$ 的随机化,插入每个元素时随机一个权值,并作为独立一组。若最后一组的最小权值小于前一组的最小权值,则将两组合并。删除时暴力将最后一块拆散,并按照插入的规则重构即可。可以证明期望复杂度仍是 $O(n\log^2n)$。

第二种是打标记。考虑对于每个被建出来的块,因为被删除的元素不会出现在区间询问内。问题出现在被删除的位置重新被填满时,此时对这个块打一个「坏」标记。查询的时候,如果这个块是坏的就向两边的儿子递归查。考虑如何让这个结构不退化,我们约定每一层至多有一个坏的块,并且要最靠右。否则就大力重构其中的另一个块。

这样就保证每一层只向一侧递归,询问的复杂度是对的。插入、删除都是在序列末尾进行,因此被打标记的节点也只存在于序列末尾。因此,要达到长度为 $len$ 的区间的重构标准,至少需要进行 $O(len)$ 次操作,重构的均摊复杂度为 $O(1)$。