数据结构相关

发表于 更新于 分类于

数据结构理论

维度

B维正交范围

对于一个\(B\)维的点\(x\),满足\(\forall 1\leq i\leq B,l_i\leq x_i\leq r_i\),称所有这样的点组成的集合为一个\(B\)维正交范围.

一维正交范围就是区间,二维正交范围是矩形,三维正交范围是立方体.

另外,如果\(l,r\)有若干个是自动满足的(所有点都满足),那么我们称它为无用限制,如果一个\(B\)维正交范围有\(k\)个有用限制,称它为\(k-side\)的.

例如,找到区间\([l,r]\)中\(<x\)的元素,这个矩形是\(3-side\)的.找到区间\([1,l]\)中\(<x\)的元素,这个矩形是\(2-side\)的.有些矩形虽然是高side的,但可能因为某些维度满足可减性,因此可能等价于一个低side的问题.

(lxl:我建议大家遇到题都要把能差分的东西差分到不能差分为止)

矩阵乘法归约

矩阵乘法

做\(n\times n\)的矩阵乘法目前得到的最优秀复杂度也是\(O(n^{2.373})\).

另外可以归约:\(01\)矩阵和整数矩阵在去除\(\log n\)后的复杂度相同.

Example

Example1(链颜色数问题)

考虑构造一棵树:他有\(\sqrt n\)个叉,每个叉上有\(\sqrt n\)个点.我们将这些叉编号为\([1,\sqrt n]\).然后我们考虑询问两个叉所组成的链的答案,设\(f_{i,j}\)表示数字\(j\)是否在\(i\)的叉上出现过,不难发现它们合并的时候要对\(f\)做或运算,\(01\)矩阵乘法相当于且运算,显然这两个运算等价,证毕.

Example2(区间逆序对)

考虑对序列和值域同时分块,考虑序列中第\(L\)到第\(R\)个块的答案,设为\(f(L,R)\),这两块间的答案设为\(g(L,R)\),显然\(f(L,R)=f(L+1,R)+f(L,R-1)-f(L+1,R-1)+g(L,R)\),而由于对值域分块,\(g(L,R)=\sum a\times b\)的形式.根据这个形式构造即可.当然这个只是简化了好多,你会发现这个东西只能处理矩阵某一行递增的情况.lxl:真正的归约是很复杂的.

Example3

平面上有若干点,两个操作:每次将横坐标小于等于\(A\)的点加上\(v\),或者查询纵坐标小于等于\(B\)的点的点权和.

这玩意显然能加上扫描线归约区间逆序对.

数据结构

分块

Example1(luoguP8527 [Ynoi2003] 樋口円香)

首先将\(a\)分块,这样对于一次修改就分成了整块和散块.散块暴力做,整块的话显然是一个位移的形式,可以直接卷积,比较简单.

不过我们先考虑个事:这么顺溜就出来了,为啥会需要分块啊?

首先看到题面的位移的形式,自然想到卷积.但问题在于有个区间,所以需要把区间处理掉.注意到每个区间是需要记录一下不同的\(L\)的,这使得这个问题只能使用分块解决.

最后还没完,这题要平衡复杂度.

设块长为\(B\),暴力处理散块的复杂度是\(O(Bm)\),处理整块的复杂度是\(O(\frac{n}{B}(m+n\log n))\).取\(B^2=\frac{n}{m}(m+n\log n)=500\)最优.

但事实上FFT肯定是很慢的,所以我开到了\(B=2048\).

即使这样,笔者还是被卡常了(哭).

Example2(luogu[Ynoi2079] riapq)

首先对于这种区间内部贡献,而且每个点由前面点的贡献,先看有没有可差分性(区间逆序对也是一个套路).

注意到是有的,这样我们就把问题转化为了\([1,l-1]\)对\([l,r]\)的贡献.

先序列分块.然后\([1,l-1]\)中的整块对\([l,r]\)的贡献是简单的:我们对每个整块开一个区间加单点查的树状数组,每次将\([1,l-1]\)中的整块的树状数组进行一个\([l,r]\)的区间加,查询的时候查一下每个整块对当前单点的贡献,这里需要对整块内部提前处理一下小于等于某个数的数量,自然可以做到\(O(Bq\log n)\)的时间复杂度和\(O(Bn)\)的空间复杂度.

问题在于\([1,l-1]\)中的散块咋办.首先\([1,l-1]\)中的散块对\([l,r]\)中的散块的贡献是好处理的,因为总共就\(O(\frac n B)\)个数字,直接全部存下来排序做归并就可以统计,时间复杂度\(O(Bq\log n)\).

现在的问题在于\([1,l-1]\)中的散块对\([l,r]\)中的整块如何贡献.能不能把\([l,r]\)的信息统计在\([1,l-1]\)的散块中呢?似乎不太行.因为散块的总数太多了.所以我们考虑把散块的信息记录在整块里.但是好像不太好记,因为你查询一个整块内的点的时候是需要判断记录的这些信息是否比它要小的,只有比它小的才能贡献.自然想到值域分块.不过还有一个问题,就是散块一共有\(\frac{n}{B}\)个,整块一共有\(B\)个,是不能一一对应着贡献的,这咋办呢?

其实挺好办的,因为散块要对一个区间有贡献,所以拿树状数组+差分统计一下就行.

最终复杂度为\(O(n\sqrt n\log n)\),需要进行一个极致卡常.

如果你写完代码测一下会发现,跑的最慢的是散块对散块的贡献,你把sort改成基数排序就行.事实上实测了一下基数排序还不如直接换成树状数组.

但即使这样,笔者现在也没过这个题(哭).

Example3([CTS2022] 普罗霍洛夫卡)

比较复杂的分块题.

放弃了,太难了.

Example4(Walking Plan HDU 6331)

类似BSGS一样分块处理即可,最后需要枚举中继点,询问部分复杂度\(O(nq)\).

Example5(P5063 [Ynoi2014] 置身天上之森)

考虑如果\(n=2^k\),很好做,因为每一层的点大小是相等的.我们对每一层分开处理,显然区间加操作也就等价于每一层的节点区间加上若干倍的\(a\)(开头结尾可能有两个需要特殊判断),用分块求区间rank的技巧就行.

但是\(n\)不一定是\(2^k\),也简单,每一层最多有两种不一样大小的点,这是经典结论.

Example6(第二分块:[Ynoi2018]五彩斑斓的世界)

大概是对于每个块处理出它的值域范围:一开始是\([1,n]\),然后每次操作都会将整个块分为两部分:\([1,x)\)和\([x,maxn]\),讨论一下\(maxn\)和\(2x\)的大小,就可以用\(\min(x,maxn-x)\)的复杂度使得\(maxn\)变成\(maxn-x\),复杂度均摊掉了.

二次离线

Example1(luoguP5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II)

简单来说就是区间逆序对数.

首先想到莫队,然后配一个树状数组就可以做到\(O(n\sqrt n\log n)\).

那我们怎么改这个东西呢?

我们注意到:我们莫队在实现的无非是俩事:一个是移动左端点的时候判断左端点对右边的贡献,一个是移动右端点的时候,由于这俩是对称的,我们只讨论左端点不动移动右端点.

考虑这个过程的答案实际上是可差分的,因为\([l,r]\)对\(r\)的贡献实际上就是\([1,r]\)对\(r\)的贡献减去\([1,l-1]\)对\(r\)的贡献,前者可以直接算,而后者呢?

我们考虑对后者再进行一次离线操作,我们把这\(O(n\sqrt n)\)次贡献查询全都记下来,然后扫描线处理一下.注意到我们只需要插入\(O(n)\)次但是需要查询\(O(n\sqrt n)\)次,所以需要使用一下值域分块平衡一下复杂度.

做到这里其实要做完了,但还没完,这里空间复杂度达到了\(O(n\sqrt n)\),有点大.咋办呢?我们发现右端点移动的时候左端点不动,并且右端点移动的是一个区间,所以我们把所有不动的左端点上记录一下右端点移动的区间即可,由于不动的左端点只有可能是查询区间的左端点,所以这里空间复杂度降到\(O(n)\).

注意到我们求出的是两个查询的答案的差分,最后还需要做一下前缀和求答案.

二维分块

我们现在有一个需要维护的\(n\times n\)的平面,我们现在对其进行分块:

  1. 将平面分成\(n^{\frac{1}{2}}\)个\(n^{\frac{3}{4}}\times n^{\frac{3}{4}}\)的\(A\)块,以\(A\)块为单位做二维前缀和.
  2. 每个\(A\)块内部分成\(n^{\frac{1}{2}}\)个\(n^{\frac{1}{2}}\times n^{\frac{1}{2}}\)的\(B\)块,在\(A\)块内部以\(B\)块为单位做二维前缀和.
  3. 将整个平面横着分别分成一个个\(n\times n^{\frac{3}{4}}\)的\(C\)块.(竖着也要分成一个个\(n^{\frac{3}{4}}\times n\)的块,是类似的,略去)
  4. 每个\(C\)块内部分成\(\sqrt n\)个\(n^{\frac{3}{4}}\times n^{\frac{1}{2}}\)个\(D\)块,在\(C\)块内部以\(D\)块为单位做二位前缀和.

注意到修改一个点的时候,需要更新三次二位前缀和,每次复杂度\(O(\sqrt n)\).同时注意到空间复杂度是\(O(n)\)的.

查询显然是分四种情况讨论:\(A,B,D\)块都可以快速求得答案,接下来只需要做一下散块就行.

那散块怎么做呢?我们考虑一个特殊情况:修改点的纵坐标以及横坐标两两不同,或至少一个坐标只对应\(O(1)\)个点.

如果查询的时候,也仍然是满足查询的一个\(l\)对应\(O(1)\)个\(r\),我们就可以枚举一个点被哪些查询查到了散块,显然只有可能有\(O(\sqrt n)\)个查询,记录一下即可.这样就做到了\(O(\sqrt n)\)单点改,\(O(1)\)查询.

如果我们一开始不做二维前缀和,就可以实现\(O(1)\)单点改,那这种情况下如何实现\(O(\sqrt n)\)求和呢?首先还是可以\(O(\sqrt n)\)求出整块的和.

横着和竖着的散块相同,只讨论横着的.由于横着的散块高度\(<n^{\frac{1}{2}}\),我们就可以在每次查询的时候用\(\sqrt n\)的复杂度枚举一遍横纵坐标在这个区间的点然后暴力判断即可,也可以\(O(\sqrt n)\)求散块.

Example1(luoguP7448 [Ynoi2007] rdiq)

首先注意到这个问题严格难于区间逆序对,想到二次离线莫队.

开始做二次离线,发现问题在于我们需要求出右端点移动的时候,找到新增了多少个本质不同的逆序对.设上一个和\(a_r\)颜色相同的点是\(r'\),则显然新增的逆序对只可能出现在\([r',r]\)中.

由于我们现在在保证左端点不动,于是我们考虑对于每种颜色,找到其在这个左端点后第一次出现的位置,并且只在这个位置贡献答案.这里其实已经可以扫描线了,套一下二次离线,把点扔到二位坐标系上.

现在问题在于,我们需要从\(n\rightarrow 1\)扫左端点,总共做\(O(n)\)次单点修改,做\(O(n\sqrt n)\)次矩阵查询.

现在我们要查询的也就是左下角为\((r'+1,a_r)\),右上角是\((r,\infty)\)的矩阵.

这个东西其实已经可以做高维前缀和了.为了使答案更显然,我们令\(rev(x)=n-x+1\).然后将所有点的纵坐标\(rev\)掉,现在我们要查询的也就是左下角为\((r'+1,1)\),右上角是\((r,rev(a_r))\)的矩阵,这玩意可以拆前缀和拆成形如左下角是\((1,1)\),右上角是\((i,rev(a_i))\)的矩阵.也就是说我们的\(O(n\sqrt n)\)次矩阵查询本质上只有\(O(n)\)种.

拆到这里发现其实到这一步\(a_r\)和\(a_{r'}\)是否相等已经不重要了,可以用一下基数排序让他俩有一定的差异.

然后上二维分块.

Example2(luoguP8530 [Ynoi2003] 博丽灵梦)

首先自然的想法是拿莫队扫掉\([l_1,r_1]\)这一维.

这样我们的问题转化为:每次插入/删除一个点,求一个类似区间颜色数的东西.

那么这个东西咋做呢?

首先我们考虑插入/删除的本质,把第二维\([l_2,r_2]\)扔到二维平面上,那本质也就是需要寻找前驱后继,然后对一个矩形做加法,查询的时候单点查询,可以配个树套树解决这个问题.

有没有什么好办法?先考虑对矩形做加法然后单点查询这个操作看上去很蛋疼.我们考虑把它转化为单点加法矩形查询.这个做法比较显然:如果没有相同的只贡献一次的限制,我们就可以直接对于每个点\((a,a)\)上加上一个相应的\(b\),然后每次查询矩阵即可.但是有了限制怎么办呢?我们考虑在每两个相邻的点\(A(x_1,x_1)\)和\(B(x_2,x_2)\)之间的\((x_1,x_2)\)上加上一个\(-b\),不难发现这样就满足了条件.

分析一下我们现在需要做的东西:

  1. 莫队时查询一个点的前驱后继,这个操作就需要\(O(1)\)完成.
  2. \(n\sqrt n\)次单点修改,这个操作需要\(O(1)\)完成.
  3. \(n\)次矩阵求和,这个操作需要在小于\(O(\sqrt n)\)的时间完成.

对于第一个问题,我们可能会想到用链表来解决.但问题在于链表难以支持插入操作.不过问题不大,我们有回滚莫队.这样就可以实现只删除不插入,解决了问题.

而后半部分是一个经典的二维分块.

简单来说,我们首先需要猜出时间复杂度为\(O(n\sqrt n)\),然后用到莫队,然后用二维平面表示这个问题,发现直接做不太能做,想到一步转化,转化后的问题的一半可以直接套二维分快.最后想到前半部分可以用回滚莫队+链表解决.

trie树

Example1([2019zrtg十连测day1]set)

首先反应是扔到trie上然后异或就是打个tag,但是\(+1\)很难处理,因为它形如在trie上找到所有长度连续为\(1\)到叶子的链并且全部翻转,不过打一下tag应该也能做.

更简单的做法是,我们考虑从小到大插入数字.这样异或几乎没有影响,但是\(+1\)的话就相当于反转一条从根开始均为\(1\)的链,这个东西更为好做.

线段树

普通线段树

Example1(luoguP6780 [Ynoi2009] pmrllcsrms)

感觉这题比较厉害.

先扔做法:对\(c\)分块,这样答案就是块内和块间的最大值.对于每个块都可以用线段树维护最大值,然后最后再求\(\max\).而对于块间如何做呢?

我们设\(suf_i\)为前一个块的后\(i\)个数之和,\(pre_i\)为后一个块的前\(i\)个数之和.注意到我们要求的就是\(\max\{suf_i+pre_j|i+j\leq c\}\).这个咋做呢?

你注意到这个\(i+j\leq c\)的限制非常的奇怪,我们如果想处理两个东西,自然想让这两个东西联系越紧密越好,但是这个联系就特别奇怪.但没关系,我们注意到如果用\(j\rightarrow c-j+1\)的话,这个限制就转化为了\(i+c-j+1\leq c\),也就是\(i<j\),这个限制就可以放到线段树上维护了.

仔细思考这个过程:线段树只可以维护有大于小于的限制的两个数,而不能维护和区间长度有关的条件.但如果一个限制和区间长度有关,可能可以通过翻转之类的操作取消掉区间长度.

这个问题解决了,我们再回到一开始:为啥要对\(c\)分块?

一方面,题目中的\(c\)是给定的.另一方面,我们注意到我们需要维护一个和\(c\)有关的东西,而如果没有\(c\),或者说\(c=n\)的时候,这个东西是好维护的:一般的区间最大子段和其实暗含了\(c=n\)的条件.考虑到这一点,对\(c\)分块就合情合理了.换句话说,分块其实有两种用途:一种是平衡暴力的复杂度:它可以让一些和块长有关的暴力复杂度降低.另一种用途是保证某个东西的合法性.

一个需要注意的事是,由于我们最后查询的是一个区间,所以对于块间的处理是需要处理区间的.不过我选择将\(a[l-1]\)和\(a[r+1]\)都加上一个极大值.

但是啊,但是.我们发现我们一开始是需要把块间做线段树的那个\(maxn\)设成\(-\infty\)的.如果这两个东西设成等大的\(-\infty\),就会出现错误,为啥呢?

因为一开始这样会使得运算过程中有可能出现比\(-\infty\)还要小的数字,最底层的\(maxn\)有可能覆盖掉上面的.

线段树分治

大概就是用到了线段树结构进行操作,通常用来处理存在区间的问题.

之所以说它是线段树分治而不是一般的分治,是因为有的时候我们还可以利用线段树的结构.

Example1([2022qbxt国庆Day1]dottlebot)

注意到每个点其实只需要找到\([i-r_i,i-1]\)和\([i+1,i+r_i]\)这两段的最大值,设为\(x\),则最后的答案就是\(\max\{a_i+x\}\).

思考这个过程,我们将\([i-r_i,i-1]\)和\([i+1,i+r_i]\)这两条线段以\(a_i\)的权值放到线段树上.具体地,我们在线段树的每个节点都开一个堆存储覆盖了这个节点区间的线段的权值.然后利用线段树求出每个区间的\(a_i\)的最大值,在节点处和堆中元素一起更新答案即可.

线段树上二分

Example1([2022qbxt国庆Day3]analysis)

考虑全局的和是\(sum\),则我们要在这些数中找到一个分界点,使得左边的和大于等于\(sum\),然后再考虑能不能将右边移动一个过去.

先把数据离散化,那么这就是一个值域线段树上二分的过程.

另外值得一提的是,考虑树状数组的形态也即线段树删去所有的右儿子,因此树状数组上也是可以二分的.

Example2

给定\(a_i,b_i\),选定至多\(k\)个位置使这里的值为\(a_i-b_i\),其它位置的值是\(a_i\),最小化最大子段和.

考虑先二分再贪心:二分一个值,然后看如果需要使得答案小于等于这个值,最少需要用多少次操作.这个咋做呢?一个想法是,我先从左到右去扫一遍,然后每次如果当前最大后缀和大于二分的\(mid\),我们就需要找一个位置使得把这个位置改掉后,最大后缀和最小.

首先来看这个为什么是正确的.考虑后面的最大后缀和是会继承前面的最大后缀和的,因此让当前局面最小一定更优秀,并且每个位置选中的代价是相等的,那自然要选择贡献最高的那个.

显然,如果选择一个改掉的话,我们需要求出\(\min_{k=1}^r\{\max(\max_{i=k+1}^n\{sum_{i}\},-b_k+\max_{i=1}^k\{sum_i\})\}\).注意改掉一个位置后要把它的\(b\)变成\(0\).

那么什么样的\(b\)有可能是我们要选中的呢?显然可能被选中的\(b\)一定是一个单调下降的序列中的某个,因为同等大小,选后面一定更优秀.上面那个式子我们是难以快速维护的,但如果我把它改成:\(\min_{k=1}^r\{\max(\max_{i=k+1}^n\{sum_{i}\},-\max_{i=k}^n\{b_i\}+\max_{i=1}^k\{sum_i\})\}\),你会发现前者是一个单调不升的序列,后者是一个单调不降的序列,现在我们想要让它们的\(\max\)尽量小,这玩意显然可以做线段树二分.

上面那个东西也就是: \[ \min_{k=1}^r\{\max(sufmax(sum)_{k+1},-sufmax(b)_k+premax(sum)_k\}\\ =\min_{k=1}^r\{\max(sufmax(sum)_{k+1},-\max(sufmax(b)_{k+1},b_k)+premax(sum)_k\}\\ \] 这样就可以在交界点更新答案.

另外,我们实际上更新答案会用到实际上找到的最小的\(k\)后面最大的\(b\),这是为啥呢?首先这样的确是更优秀的解,而且我们发现,我们的确有可能找到更靠前的位置,如果往前的挪动不影响\(sufmax (b)\)的话.那有没有可能跳出了这一段,来到了更靠后的地方呢?这显然也不会,因为我们只找到最后面第一个处于当前分段函数的\(b\),这个\(b\)必然存在.如果它所在的sufmax和premax不一样,那么会是一个更优秀的解,压根不可能找到前面.

线段树合并

线段树维护矩阵乘法

吉司机线段树

李超线段树

珂朵莉树

Example1(luoguP8512 [Ynoi Easy Round 2021] TEST_152)

首先有经典套路:赋值操作有用的只有最后一次.

所以考虑扫描线,扫右端点的时候直接用珂朵莉树做.这样就剩下左端点的问题,因为有珂朵莉树,所以再开以时间为下标的数据结构就能处理.

猫树

KD-Tree

处理\(K\)维正交范围(给定\(n\)个有意义的点)在线修改查询的数据结构,是一棵二叉树.单次复杂度\(O(n^{1-\frac{1}{k}}+\log n)\).(单调修改复杂度只是\(O(\log n)\))

离线情况下通常可以用cdq分治代替.

如果要支持动态插点,可以使用复杂度不正确的替罪羊树重构+kdtree.

1D-Tree

也就是线段树.

2D-Tree

建树的时候,对于每一维轮流考虑,每次考虑将这一维上的坐标的中位数的点(基准点)找到,左右分治下去(下一层要考虑另一维)处理.查询和修改都是类似的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
struct KD_tree{
	int son[2];
	int x,y;
	int siz;
	int f;
	int l,r,u,d;
}tr[qwq<<1|1];
int cur[qwq<<1|1];
int clen;
struct P{
	int x,y;
}p[qwq<<1|1];
bool cmpx(P a,P b){
	return a.x<b.x;
}
bool cmpy(P a,P b){
	return a.y<b.y;
}
ll mabs(ll x){
	if(x>0)return x;
	return -x;
}
void pushup(int cnt){
	tr[cnt].l=tr[cnt].r=tr[cnt].x;
	tr[cnt].d=tr[cnt].u=tr[cnt].y;
	tr[cnt].siz=1;
	if(tr[cnt].son[0]){
		tr[cnt].l=std::min(tr[cnt].l,tr[tr[cnt].son[0]].l);
		tr[cnt].r=std::max(tr[cnt].r,tr[tr[cnt].son[0]].r);
		tr[cnt].d=std::min(tr[cnt].d,tr[tr[cnt].son[0]].d);
		tr[cnt].u=std::max(tr[cnt].u,tr[tr[cnt].son[0]].u);
		tr[cnt].siz+=tr[tr[cnt].son[0]].siz;
	}
	if(tr[cnt].son[1]){
		tr[cnt].l=std::min(tr[cnt].l,tr[tr[cnt].son[1]].l);
		tr[cnt].r=std::max(tr[cnt].r,tr[tr[cnt].son[1]].r);
		tr[cnt].d=std::min(tr[cnt].d,tr[tr[cnt].son[1]].d);
		tr[cnt].u=std::max(tr[cnt].u,tr[tr[cnt].son[1]].u);
		tr[cnt].siz+=tr[tr[cnt].son[1]].siz;
	}
	return ;
}
inline ll dispp(int pa,int pb){
	return 1ll*mabs(tr[pa].x-tr[pb].x)+1ll*mabs(tr[pa].y-tr[pb].y);
}
inline ll dispm(int po,int mat){
	if(!mat)return 320051113;
	ll d=0;
	if(tr[po].x<tr[mat].l)d+=tr[mat].l-tr[po].x;
	if(tr[po].x>tr[mat].r)d+=tr[po].x-tr[mat].r;
	if(tr[po].y<tr[mat].d)d+=tr[mat].d-tr[po].y;
	if(tr[po].y>tr[mat].u)d+=tr[po].y-tr[mat].u;
	return d;
}
bool get_var(int l,int r){
	double avx=0,avy=0;
	for(int i=l;i<=r;++i){
		avx+=p[i].x;avy+=p[i].y;
	}
	avx/=(r-l+1);avy/=(r-l+1);
	double varx=0,vary=0;
	for(int i=l;i<=r;++i){
		varx+=1ll*(avx-p[i].x)*(avx-p[i].x);
		vary+=1ll*(avy-p[i].y)*(avy-p[i].y);
	}
	return varx<vary;
}
int build(int l,int r){
	if(l>r)return 0;
	int mid=(l+r)>>1;
	int cnt=cur[mid];
	tr[cnt].f=get_var(l,r);
	if(tr[cnt].f)std::nth_element(p+l,p+mid,p+r+1,cmpy);
	else std::nth_element(p+l,p+mid,p+r+1,cmpx);
	tr[cnt].x=p[mid].x;tr[cnt].y=p[mid].y;tr[cnt].siz=1;
	tr[cnt].son[0]=build(l,mid-1);
	tr[cnt].son[1]=build(mid+1,r);
	pushup(cnt);
	return cnt;
}

笛卡尔树

Example1([CFgym101613]Factor-free tree)

首先有一个自然的想法是随便找一个和整个区间都互质的数,然后把序列分成左右两端向下递归.对于一棵构造出来的二叉树,它的复杂度就是\(\sum dep_u\),是可以被卡成\(O(n^2)\)的.

但我们考虑类似dsu on tree的做法,我们每次找到一个点,它将一个区间劈成了两部分,我们把小的那部分的贡献删去,然后做大的那部分.在递归过程中把大的那部分的贡献逐渐消磨掉.最后再做小的那部分,这样就类似于启发式合并的过程,复杂度就正确了.

Example2(23省选第一轮集训day5C)

注意到最小值的条件是容易满足的.

考虑枚举以每个点为最大值转移的区间,假设为\([l,r]\),这样会有:\([l-1,i-1]\rightarrow [i,r]\).注意到我们可以选择其中较短的区间来更新零一个区间或被另一个区间更新.

单调队列

Example(loj3151)

首先自然地,我们设\(f_{i,j}\)表示前\(i\)个测试点已经分成了\(j\)段的方案数,然后做转移,复杂度\(O(T^2S)\).

接下来咋优化咧?决策单调性!

嘶这题好像不满足决策单调性(这个故事也告诉我们不要看到\(k\)最短路就想决策单调性).

冷静一下,首先如果我把\([l,r]\)分到一段里,那这一段的答案和啥有关?显然只和有多少个人在这段区间中没挂分有关.对于一个右端点\(r\),我们不妨枚举有多少个人会在它所在的子任务挂分.显然,在左端点在一个区间内的时候,这个子任务会有一定的人挂分.而且随着现在右端点的移动,这个区间的左右端点都是单调不降的.那我们对于每种人数做单调队列维护即可.

树套树

解决矩阵修改+单点查询或单点修改+矩阵查询问题.

Example1

维护一个序列支持把\(x\)位置的值改为\(y\)或查询一个区间中小于\(y\)的数个数.

用树状数组维护平衡树,每次在树状数组上对应的节点修改即可.

Example2(Luogu4054 [JSOI2009]计数问题)

乍一看是动态三维问题.

相等维度是特殊的,我们开\(100\)个二维数据结构处理值不同的情况,这样就是二维.

数据结构常见套路

分开考虑

Example1(P6105 [Ynoi2010] y-fast trie)

考虑只有两种可能:

  1. \(x+y<C\),取\(x+y\)作为答案.
  2. \(x+y\geq C\),取\(x+y-C\)作为答案.

后者只需要取出最大的两个数即可,至于前者,考虑将所有数字分成两个集合,一个集合只在\([0,\lceil\frac{C}{2}\rceil)\)中,一个集合包含剩下的数字.对于第一个集合,我们只需要取出其中最大的两个数字就行.接下来的问题是怎么处理跨越两个集合的答案.考虑将每个点对应的答案配对,显然每个点能影响到的点是一段区间,删除时暴力修改.

另外,\(x+y<C\)也就是\(x<C-y\),我们把第二个集合中的元素全部变成\(C-y\)后插入,只需最小化\(C-x-y\),这个只需要维护最大的\(x\)和最小的\(C-y\)就行.

合并信息

lxl:这种问题主要需要解决三件事:标记对标记可合并,标记对值可合并,值与值可合并.

Example1([HNOI2011]括号修复 / [JSOI2011]括号序列)

注意到只要知道区间的最小前缀和以及区间的和,这个题就做完了.我们只需要维护这两件事.区间的和显然是好维护的,难以维护的是最小前缀和,我们来分开看每个操作:

替换:简单的.翻转:不太好做,尝试维护一下最小后缀和.反转:需要维护最大前缀和,进一步需要维护最大后缀和.

这样就可以更新答案了.

Example2(P4198 楼房重建)

左右维护单调栈合并,但这样复杂度肯定不对.

怎么办呢?我们可以用\(O(\log n)\)的单次pushup操作,也就是维护一下每个节点所代表的区间的答案和最大值,不断递归右子树(或左子树)判断.

Example3(CF1017G)

设\(w_i\)为从上往下延伸到\(i\)这个点后,还能多往下延伸多少,一开始\(w\)都是\(-1\),每次操作会让\(w+=1\).树链剖分维护子段最大非空后缀和.

去除冗余信息

Example1(luoguP6617)

自然的想法是考虑找到每个点前面第一个和它之和为\(w\)的数字,但这样就炸了,因为每修改一个点可能要影响\(O(n)\)个点的答案.

我们注意到一个事实:我们也可以找到每个点后面第一个和它之和为\(w\)的数字,而显然只有两个数互相匹配才可行.如果\(i<j<k,(i,j),(i,k)\)分别配对,那么显然\((i,k)\)没有用.这样每个点只有\(O(1)\)个匹配了.

set维护颜色

Example1(luoguP5278 算术天才⑨与等差数列)

首先考虑\(k=1\)怎么做,显然找一下区间最大值和区间最小值,然后就只需要判断区间内有没有重复元素,经典套路:set维护颜色,这样可以处理出每个点上一个和它相同颜色的点,拿线段树维护它的最大值.

\(k\ne 1\)怎么办呢?考虑这只是相当于要判断一下这个区间内的数字是否在\(\bmod k\)意义下全部相等,维护差分数组的区间\(\gcd\)就行.

复杂度均摊

Example1(CF702F T-Shirts)

看到这个感觉很奇怪,想想好像也没有什么快速tag算法.

我们考虑对人建平衡树,然后按照顺序买衣服,每次找到所有能买这件衣服的人,显然是平衡树的某棵子树.但是,这棵子树在买完衣服后可能就不满足顺序了,那怎么办呢?能不能暴力重构一波?

事实上是可以的,对于一件价格为\(q\)的衣服,\([0,q)\)的人肯定买不了,\([q,2q-1]\)的人买完后,手上的钱至少减半,我们暴力处理,至于\([2q,+\infty)\),显然买完后不会对其形态有什么影响,打个tag.

Example2(uoj228)

一个自然的想法是暴力开根号,它会迅速缩短两个数之间的差.但可能也不能缩到\(0\),那怎么办呢?当我们发现这个区间的最大值和最小值开根号后的差不变了,我们就把开根操作改成区间减法就行了.

loj6029是等价做法.

Example3(Luogu 4690 [Ynoi2016]镜中的昆虫)

维护每个点的颜色相同的前驱,单点修改的话就是简单树套树.

然后区间推平可以用颜色块均摊(同一个颜色块内只需要改开头元素,剩下的都是\(pre[i]=i-1\)).

根号分治

Example1(luoguP7722 [Ynoi2007] tmpq)

这个题告诉我们一个故事:有的时候,有的条件可能真的没用.

直接把题目改成:每次修改\(a,b,c\)中的某个数,求.

Example2

对于一个数字\(x\),每次随机在\([1,x]\)中一个数\(y\)并令\(x\leftarrow x\bmod y\),初始值为\(n\),求期望几次能变成\(0\).

注意到如果\(y\)很小就直接做,\(y\)很大的话\(\lfloor\frac{x}{y}\rfloor\)很小,暴力做数论分块.

Example3

给定一棵树,每次修改树上某个点的权值,或询问某个点周围的点的权值和.

度数大的点在修改的时候改,度数小的在询问的时候做.

Example4

给定序列,每次询问给出两个数字\(x,y\),求最小的\(|i-j|\)满足\(a_i=x,a_j=y\).

对于出现次数大的,处理出它和所有数字的答案.

如果\(x,y\)出现次数都少,就在做的时候直接归并.

Example5(SHOI2006 Homework)

首先对于\(Y\)很小的情况直接预处理就行,每次插入的时候更新答案.

对于\(Y\)很大的情况,\(\frac{n}{Y}\)一定很小,我们不断查询大于等于\(kY\)的最小元素即可,这个可以值域分块来根号平衡做到\(O(1)\)查询,\(O(\sqrt n)\)单点修改.具体地,我们对每个块处理出大于等于这个块的最小的\(X\),以及块内每个点后面最小的\(X\)(必须在块内),然后定位到\(kY\)的块.

Example6

给定\(n,m\),以及序列\(a\)和长度为\(n\)的排列\(y\),你需要回答\(m\)个询问.对每个询问,给定\(l,r\),查询: \[ \sum_{i=1}^n\sum_{j=i+1}^n[a_i=a_j]\prod_{k=i}^j[l\leq y_k\leq r] \] 注意到\(y_i=i\)的时候,这题等价于小Z的袜子.因此这题不会低于根号复杂度.轮流猜算法,猜到根号分治.

首先有一个性质:对于一对点\((x,y),a_x=a_y,\nexists x<z<y,a_z=a_x\),对于\((x,y)\)这个区间内部的点,它们其实是可以缩起来的!(比赛的时候没想到呜呜)具体来说,我们只需要保留它们中最大的那个和最小的那个就行.

接下来,对于出现次数大于\(\sqrt n\)的数字,它们最多只有\(\sqrt n\)个,考虑莫队复杂度\(O(n\sqrt m+m)\),因此我们可以对每个分别做莫队,总复杂度\(O(n\sqrt m+m\sqrt n)\),注意用基数排序,甚至不能用桶排.

对于出现次数小于\(\sqrt n\)的数字,这些数字一共最多有\(n\)个,每个点暴力配对就有\(O(n\sqrt n)\)个点对,然后\(O(m)\)次询问,用根号平衡做扫描线,这里复杂度\(O(n\sqrt n+m\sqrt n)\).

重链分治

Example1(Luogu5314 [Ynoi2011]ODT)

其实不是根号分治,但是差不多,扔这里了.

给一棵树,边权为\(1\),支持把一条链上所有点加上\(k\),或者查询距离一个点\(<=1\)的所有点的点权\(kth\).\(n\leq 2\times 10^5\).

每个点周围的点一共有三种可能:父亲,重儿子,轻儿子,特判重儿子和父亲,然后处理出所有轻儿子的情况,这个怎么做都能做(大不了把所有轻儿子全扔平衡树里),然后重链剖分的时候只会改\(O(\log n)\)个轻儿子.

扫描线

一维扫描线

最经典的应用是对于一个\(B\)维的静态问题,我们可能可以用扫描线扫掉一维,让它变成一个\(B-1\)维的动态问题.不过扫描线处理的时候可能需要是低\(side\)的问题,具体情况具体分析.

主席树通常就是解决强制在线不能处理扫描线的问题.

另外,通常认为时间也是一维,也就是即使是动态问题也一般是等价于对时间跑了扫描线.

二维扫描线

也就是莫队.

Example

Example1(CF1609F Interesting Sections)

首先枚举每个数的\(popcount\),相当于每次将一些点标记为关键点,然后查询有多少个区间满足区间最大值和最小值都是关键点.

可以求出每个点\(x\)作为最大值的影响区间\([l,r]\),也就是如果一个区间左端点在\([l,x]\),右端点在\([x,r]\)即可满足条件.我们考虑放入一个左下角坐标为\((l,x)\),右上角坐标为\((x,r)\)的矩阵.最小值也是同理的,最后也就是求所有最大值矩阵和所有最小值矩阵的交.注意到如果两个点相同,我们规定一下在前面的更小,那么最大值矩阵两两不交,最小值矩阵也两两不交,就是一个最简单的扫描线问题了.

Example2(CF833E)

离散化,设\(S=\{l\}\cup\{r\}\),考虑用\(len_i\)表示\(i\)节点及以前最多能有多少阳光.我们考虑用\(len_{i-1}\)更新\(len_i\),如果\([i-1,i]\)没被覆盖,显然直接加上这段的长度.如果\([i-1,i]\)被覆盖大于两次,那显然直接继承\(len_{i-1}\).

先考虑\([i-1,i]\)被两朵云覆盖了怎么办,我们考虑用\(h_{j,k}\)表示当前被且只被\(j\)和\(k\)共同覆盖的区间长度,不难发现\(h_{j,k}\)有值的地方很少,用map.然后还要加上它们各自的贡献,用\(g_j\)表示当前被且只被\(j\)覆盖的区间长度,这样就可以计算答案.而这两个辅助数组也可以在判断\([i-1,i]\)是被一朵云还是被两朵云覆盖的时候更新掉.

如果\([i-1,i]\)被一朵云覆盖了怎么办呢?我们考虑把这朵云杀了,但我们还可能杀掉前面的某一朵云,假设为\(k\),那么就有两种情况:要么这两朵云有交,要么无交.

先考虑无交的情况,这个时候答案显然是\(g_j+g_k\),用线段树处理出当前代价和小于等于\(C\)的\(k\)的\(g_k\)的最大值就行.

再考虑有交的情况,答案应该为\(g_j+g_k+h_{j,k}\),我们在每次遇到\((j,k)\)的时候都在对方那里打个tag就好,也就是对于每个\(j\),处理出和它有交的云中\(g_j+g_k+h_{j,k}\)的最大值.虽然这些值都会变,但是只会变大,因此可以处理.

那么怎么判断两朵云有交呢?我们不用判断两朵云是否有交,因为前者一定没有后者优秀.不过需要判断两朵云不能是同一朵,这个存一下次大值就可以解决.

这样就转移完了这个题,挺厉害的.

Example3(loj3489)

时间也是一维,扫序列维护时间,线段树二分就可以解决.

具体地,我们需要对每个询问找到这个询问前最近的队列为空的时刻,然后这个时刻后面的答案就可以直接拿前缀max二分,问题在于怎么求这个时刻.

这个时刻也是好求的,它一定是前缀的最小值(这个点一定清空了,这个点后面的数比它小,因此这个点变成\(0\)后那些数一定没清空).

Example4(luoguP7709 「Wdsr-2.7」八云蓝自动机 Ⅱ)

如果初始序列全为\(0\):

倒着扫操作序列,维护当前还没有得到答案的询问,每次找到一个操作一定将整个区间的询问全部得知了答案.

不然不会做.

Example5(luogu3863)

仍然是个数据结构维护时间维,扫描线扫序列维的东西.

Example6(qoj6304)

考虑横纵坐标是对称的,因此我们只需要考虑两横一竖的情况和三条横的情况.

先做三条横,枚举中间的那个横的位置,剩了一段前缀和一段后缀需要覆盖,这个可以前后缀预处理.

然后是两横一竖,扫竖线,问题转化为动态加入删除区间,求当前用两个点覆盖所有区间的方案数,不妨设这两个点是\(L<R\),自然有\(L\leq \min\{r_i\},R\geq \max \{l_i\}\),那么当我们确定\(L\)后,我们有\(R\in[\max\{l_i\},f(L)]\).接下来我们考虑如何计算\(f(L)\).

注意到\(L<l_i\Rightarrow R\leq r_i\),我们考虑将\(l_i\)这个点的权值设成\(r_i\),那么我们要做的就是一个后缀最小值求和,用楼房重建.

莫队

回滚莫队

带修莫队

也就是维护三维的扫描线,根据KDT不难发现复杂度是\(O(nm^{\frac{2}{3}})\),\(B=n^{\frac{2}{3}}\),排序原则是\((ls,rs,t)\),复杂度算一算就知道是对的.

树上莫队

二次离线莫队

这个直接拿区间逆序对当例子记笔记好了.

如果我们用正常的莫队做区间逆序对,我们会得到带个\(\log n\)的复杂度:也就是每次扩展一个数,计算它对答案的贡献,这个是必须带\(\log n\)的,而且查询次数等价于移动次数,我们甚至不能用根号平衡.

那么怎么解决这个问题呢?我们现在无非是有\(n\sqrt n\)次询问,每次询问\(f(l,r,r+1)\)表示区间\([l,r]\)对\(r+1\)的逆序对贡献.考虑差分成\(f(1,r,r+1)-f(1,l-1,r+1)\),前者显然可以迅速求出.而后者的右端点需要移动\(n\)次,需要查询总共\(n\sqrt n\)次,zhe’ge

Example

Example1([Ynoi2016]这是我自己的发明)

dfn将子树转序列,注意到换根无非是把一个序列拆成了两个序列,这是好做的.不过这玩意都\(4-side\)了,但是有可减性,减成\(2-side\)就能莫队了.

Example2([HNOI2016]大数)

区间子区间问题对于莫队是有一个套路的:即转化为二元组计数问题.

具体怎么做呢?首先这个题我们特判掉\(p=2\)和\(p=5\)的情况,这个只需要判断个位数就可以.然后我们考虑求每个点后缀代表的数字\(\bmod p\)的值,设为\(suf_i\),假设存在两个点\(l,r\)满足\(p|(suf_l-suf_{r+1})\),那么\([l,r]\)就是合法的,这是自然的,也就等价于\(suf_l=suf_{r+1}\),相当于要对满足\(suf_l=suf_{r+1}\)的二元组\((l,r)\)计数,这个是可以用莫队维护的.

Example3(luoguP3604 美好的每一天)

类似上面那个题,用哈希(其实就是将26个字母表示成26个二的幂次)然后异或起来,和上面的题就完全一样了,做二元组计数.

区间子区间问题

求有多少个子区间满足条件.

上二维平面,子区间所代表的\((l,r)\)的点一定是在一条角平分线上的一个等腰直角三角形.

Example1(CF997E)

考虑转化为二维平面,\(a_{l,r}=maxn-minn-(r-l)\),显然只需要找到为\(0\)的操作就行,这四个数可以转化为四个矩形加法,做扫描线.

另外这里的矩阵加法有\(3-side\)的,但是可差分成\(2-side\).

时间倒流

Example1([2022qbxt国庆Day6]sgtbeats)

首先考虑:如果一个点被清空了多次,那么只有最后一次有意义.

删除操作很难做,考虑变成插入,然后就可以拿数据结构维护操作序列的后缀max,存一下每个点最后被清空的时间,然后处理即可.

Example2([WC2006]水管局长)

时间倒流,删边变加边,LCT做一下.

数据结构维护分段函数

Example1(CF1540D Inverse Inversions)

考虑对于一个数列怎么构造:假设只考虑前\(k\)个数,它们的取值是\([1,k]\),现在加入第\(k+1\)个数,由于我们知道它是前缀第几小,所以我们可以直接将它设成这个值,然后将前面所有大于等于这个值的点全都\(+1\),不难发现这一定是唯一构造.

那么我们现在要知道\(p_i\)是多少,根据上面的构造过程,首先将\(p_i=a_i\),然后不断向后遍历,每遇到一个\(a_j\),如果\(a_j\leq p_i\),则把\(p_i+=1\).

我们将数列分块,设块长为\(B\),那一个值经过一个块的时候最多加块长个\(1\).也就是经过整块的时候是一个\(B\)段的分段函数.

考虑暴力求出这个分段函数,每次询问的时候直接二分,修改的时候考虑每个块维护一个线段树,线段树的区间表示这个区间对应的分段函数.这样单点修改复杂度是\(\sum{\cfrac{B}{2^i}}=B\)的,

于是最后复杂度为\(O(T(B+\cfrac{n}{B}\log n))\),取\(B=\sqrt{n\log n}\)即可.

根号平衡

根号平衡主要用到下面四个东西:

  1. \(O(1)\)单点加,\(O(\sqrt n)\)区间和:维护块内的和即可.
  2. \(O(\sqrt n)\)单点加,\(O(1)\)区间和:维护块内和块间的前缀和即可.
  3. \(O(\sqrt n)\)区间加,\(O(1)\)单点和:差分转化为\((2)\).当然打标记也是可以的.
  4. \(O(1)\)区间加,\(O(\sqrt n)\)单点和:差分转化为\((1)\).当然打标记也是可以的.

还有一些拓展的东西:

  1. 维护值域\(O(n)\)的集合,支持\(O(1)\)插入,\(O(\sqrt n)\)查询第\(k\)小:值域分块就可以.
  2. 维护值域\(O(n)\)的集合,支持\(O(\sqrt n)\)插入,\(O(1)\)查询第\(k\)小:值域分块,然后暴力改变每个点所属的块就行.

Example

Example1(区间众数)

首先分块,处理出\(f_{l,r}\)表示块\([l,r]\)的答案.这样每次只需要加入散块中的每个数并判断答案即可,由于判断每个数在区间出现次数是\(\log n\)的,因此复杂度\(O(n\sqrt {n\log n})\).

但是可以优化,我们设\(mx\)表示当前众数出现次数,注意到我们判断一个数字在区间中出现次数是否大于\(mx\)可以\(O(1)\)判断(处理出这个数所有的出现位置),而如果遇到两个数需要对冲,显然\(mx\)增加总次数也不会超过\(O(\sqrt n)\),因此做到\(O(n\sqrt n)\).

不删除莫队也能做.

当然,如果只要求区间众数的出现次数,可以直接莫队.

Example2(CodeChef Chef and Churu)

首先发现函数是不会被修改的,因此考虑对函数分块,对于那些散着的函数肯定可以用一个\(O(1)\)查询区间和,\(O(\sqrt n)\)单点修改的进行根号平衡.

而怎么快速处理整块呢?发现函数可差分,差分后就可以算出每一个位置对这个块内的总贡献,这样就可以更新了.

Example3([Ahoi2013]作业)

莫队,发现有\(m\)次查询,\(n\sqrt m\)次移动,于是根号平衡.

Example4(Bzoj4241历史研究)

回滚莫队板子.

事实上考虑可能的答案只有\(O(n)\)种,用值域分块就可以平衡复杂度.