进阶数据结构学习笔记

来自\(\color{Gray}\texttt{SharpnessV}\)的内卷省选复习计划中的进阶数据结构。

不妨先看看前一篇\(awa\)。

像上一篇一样，先列出用到的高级算法/数据结构/思想：

• 线段树合并1,5,6
• 可持久化2,3,4,7
• 线段树上二分4,5,8
• 线段树分裂6
• 二分答案6
• 贪心7
• 堆8

下面是例题时间！

例题1

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

给你一棵树，每个节点都是有一个可重集合，每次选择一条链，向链上的每一个点的集合中都插入一个数。最后输出每个点的集合中出现次数最多的数，若有相同的输出小的。

我们将每一个修改\(x\leftrightarrow y\)树上差分后变成为\(1\to x,1\to y,1\to \operatorname{lca}(x,y)\)，即我们在\(x,y\)上各打上一个\(+1\)的标记，在\(\operatorname{lca}(x,y)\)上打一个\(-1\)，在\(fa_{\operatorname{lca}(x,y)}\)上也打上一个\(-1\)即可。

这个标记我们使用动态开点的权值线段树维护。对每一个点都开一颗权值线段树，然后对于每次修改进行单点修改同时上传标记是维护最大值。

最后统计答案，从叶子节点向上合并线段树。线段树的合并很简单，就是将一棵线段树的有用的节点的数据合并即可。

Code

例题2

P3919 【模板】可持久化线段树 1（可持久化数组）

继续使用动态开点线段树，记第\(x\)次修改/询问的根节点为\(root_x\)。

修改时，我们一般的线段树使用时是形如change(int p,int l,int r,...)这样的方式。对于需要拷贝节点的动态开点线段树呢，我们就使用change(int &p,int pre,int l,int r,...)，表示当前节点p如果需要修改的话应当从pre节点拷贝过来。

代码片段：

void change(int &p,int pre,int l,int r,int x,int v)
{
	p=copy(pre);
	if(l==r)
	{
		val(p)=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)
	{
		change(ls(p),ls(pre),l,mid,x,v);
	}
	else
	{
		change(rs(p),rs(pre),mid+1,r,x,v);
	}
}

Code

例题3

P3402 可持久化并查集

可持久化并查集基于可持久化数组。

并查集的最根本的操作是查询一个点的父亲，即\(f_x\)，可以看作是一个数组\(f\)的第\(i\)位。但是我们使用并查集是还需要用到一些优化比如按秩合并，路径压缩等。在路径压缩中，查询操作中的修改太多了，我们放弃这一种方式，而转念想一想，路径压缩是否可以用于可持久化并查集？当然可以。

在并查集上我们需要修改\(x\)的父亲\(f_x\)（不是指树的根，是直接的父亲），只需要f[x]=y。但是为了可持久化我们就损耗一定的时间（换取每一次版本保存的时间），在\([1,n]\)上的线段树进行可持久化数组那样的change(int &p,int pre,int l,int y,int pos)操作。查询f[x]也是如此(但是就不用修改了，不需要引用啥的)。

并查集还有一个操作是getf(int x)，即得到\(x\)所在的树的树根。我们暴力向上跳\(f_x\)（用上面的那种，每查询一次父亲的时间复杂度是\(O(\log n)\)的），直到\(f_x=x\)则返回\(x\)。

merge操作是基于getf和change的，就不用说了。

ask操作就getf(x)==getf(y)即可。

注意数组要开大一点，一次修改操作的时间复杂度&空间复杂度都是\(\rm O(\log n)\)的，所以总时间复杂度就是\(\rm O(m\log n)\)的。

再注意一点，change操作中，如果修改的左子树，就要把右子树直接copy过来，反之同理。所以我先copy，再进行下一层的change，反正下一层一定会新建节点的。

依照pre所在的旧版本，将p所在的新版本中的\(x\)的父亲设置成\(v\).

void change(int &p,int pre,int l,int r,int x,int v)
{
	p=++cnt;
	if(l==r)
	{
		f[p]=v;
		dep[p]=dep[pre];
		return;
	}
	int mid=l+r>>1;
	ls[p]=ls[pre];//
	rs[p]=rs[pre];//
	if(x<=mid) change(ls[p],ls[pre],l,mid,x,v);
	else change(rs[p],rs[pre],mid+1,r,x,v);
}

Code

例题4

P3834 【模板】可持久化线段树 2（主席树）

经典的问题——静态区间第k小。

我们对序列上每一个点\(x\)的前缀（记为\(pre_x\)）建立一棵动态开点权值线段树，然而发现相邻的两颗树之间只有微小的差距，有些节点是不变的。所以在建立\(pre_x\)时，我们就基于\(pre_{x-1}\)，相同的节点直接复制，有修改的节点就新建节点。同时维护\(sum_p\)权值线段树上的节点\(p\)所表示的\([l,r]\)可以中有多少个数字。

查询时，我们将询问\((l,r)\)差分为\(l-1\)和\(r\)，然后就同时在两颗线段树上进行线段树上二分。

详细地，假设当前节点是\(x\)和\(y\)，其所代表的区间皆为\([l,r]\)。那么区间\([l,mid]\)中就有\(sum=sum_{ls[x]}-sum_{ls[y]}\)个数字。假设现在是要求这个区间的第\(k\)小数，那么如若\(k\le sum\)，则第\(k\)小数在\(p\)的左子区间\([l,mid]\)中；否则就在右子区间\([mid+1,r]\)中。

我自己写了一个bug：（我是菜鸡，大佬勿喷，仅供个人记录）

void change(int &p,int pre,int l,int r,int x)
{
	if(!p) p=node(pre);//
	if(l==r)
	{
		sum[p]++;
		return;
	}
	int mid=(l+r)>>1;
    if(x<=mid) change(ls[p],ls[pre],l,mid,x);
	else change(rs[p],rs[pre],mid+1,r,x);
	upd(p);
}

这种写法中，无论如何p都应该要从pre复制过来，不然要是一个点的ls不为0，向左儿子change时，就会直接在旧版本上change了。

正确写法：

void change(int &p,int pre,int l,int r,int x)
{
	p=node(pre);
	if(l==r)
	{
		sum[p]++;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) change(ls[p],ls[pre],l,mid,x);
	else change(rs[p],rs[pre],mid+1,r,x);
	upd(p);
}

Code

例题5

P3224 [HNOI2012]永无乡

有一堆点，每个点都有点权（保证没有两个点的点权是相同的，反正就是直接给排名啦）。每次有两个操作，一是将两个点之间连边，二是询问一个点所在的连通块中排名第\(k\)小的点的编号，若不存在则输出\(-1\)。

这两个操作感觉很模板：合并两个连通块，用并查集维护连通性，然后对于排名可以用线段树合并来维护；询问排名第\(k\)小，就类比P3834 【模板】可持久化线段树 2（主席树）中的线段树二分即可。

Code

例题6

P2824 [HEOI2016/TJOI2016]排序

给你一个序列\(a\)，有\(m\)次操作，每一次操作将区间\([l,r]\)重新排序(0是升序，1是降序)。最后输出\(a_q\)。

\(n,m\le 10^5,1\le q\le n\).

看见只有一个询问，当然是从这里入手了。

考虑二分答案：假如我们已经知道了修改最后，\(a_q=ans\)，那么我们可以二分这个\(ans\)不是嘛。如何check\(ans\)是否合法呢？

首先要知道一个\(trick\)：可以发现对\(0/1\)序列排序就相当于将所有\(0\)全部放到了\(1\)的左边，也就相当于先记录这个区间的\(sum\)，后将\([l,r-sum]\)覆盖为\(0\)，将\([r-sum+1,r]\)覆盖为\(1\)，这个可以用线段树在\(O(\log n)\)的时间复杂度内完成一次修改。

如果我们已经知道了答案是\(ans\)，那么我们不在关心其他一对值之间的大小关系，只关心其他值与\(ans\)的相对关系。所以我们将小于\(ans\)的所有数全部变成\(0\)，大于等于\(ans\)的数全部变成1，然后看\(a_q\)是否为\(1\),是\(1\)的话说明\(ans\)可能偏大。否则\(ans\)一定偏小。

当然也有用线段树分裂&合并在\(O(m\log n)\)的时间复杂度内处理多组询问的算法，这里继续留白\(\color{gray}awa\)。

Code

例题7

P3293 [SCOI2016]美味

给你一个序列\(x\)，每一次询问

\[\max_{i=l}^r(a+x_i) \operatorname{xor} b \]

看到这个题面，不妨先想一想最简单的没有\(l,r,a,b\)这些参数我们可以暴力扫建立一棵0/1trie然后在trie上面贪心向1的那一条边走，没有1边才走0边。

加了一个\(b\)怎么办？看看\(b\)的当前一位如果是0的话还是优先向1否则优先向0就是了。

有了\([l,r]\)怎么办，拿主席树来维护吧！将两个线段树相减就可以得到一段区间中的数了。查询是否有1这一条边，发现在数值上相当于查询\([now,now+(1<区间中是否存在数，这个就可以用线段树查询了！

有了个\(a\)？每次查询的时候加上个\(a\)不就好了？

最后算出来的答案别忘记\(\operatorname{xor}b\).

Code

例题8

给你一个序列\(a\)，定义一段区间的价值为\(val[l,r]=\oplus_{i=l}^ra_i\)每次询问区间\([l,r]\)中前\(k\)大的不同区间的价值之和。

\(1\le n\le 5\times 10^5,1\le k\le \min{\frac{n(n-1)}2,2\times 10^5},0\le a_i\le 2^{32}-1\).

既然是要选择区间，那么我们将区间转换为前缀形式，即设\(s_i=val[1,i]\)，则\(val[l,r]=s_r-s_{l-1}\)。

现在题目变成：给定一个\(s_i\)数组，且\(s_0=0\)，求\(0\le i时\(s_i\oplus s_j\)的前\(k\)大种取值之和。

\(i可以变成\(i\neq j\)，最后选择两倍的\(k\)并将和除以二即可。当\(i=j\)时\(s_i=s_j\to s_i\oplus s_j=0\)，一定不会成为答案，所以这个约束也可以去掉。

现在题目变成：给定一个\(s_i\)数组，且\(s_0=0\)，求\(s_i\oplus s_j\)的前\(2k\)大种取值之和的一半。

如果把\(s\)插入到01 trie中，那么没给定一个\(k\),我们可以在\(O(\log w)\)的时间复杂度内找到与一个数异或结果第\(k\)大的数。方法类似于线段树上二分，可参见例题4和例题5。

这时，我们用一个大根堆来计算答案。堆开始时放入\(\forall s_i\)与\(s\)中的元素异或的最大值(用\(01trie\)查询)同时保存信息\(i\)和\(rnk\)。每一次取出堆顶，假设堆顶是\((x,i,rnk)\)，把\(x\)加入答案，找到\(s_i\)与\(s\)中的元素异或的第\(rnk+1\)大值变成新的\(x\)并将\((x,i,rnk+1)\)放入堆中。进行\(2k\)次操作，那么取出的依次就是\(s\)中元素两两异或的前\(2k\)大值，再除以二即可。（我个人感觉这部分的思路来自一种sb单调性，同P2048 [NOI2010] 超级钢琴）

时间复杂度\(O(n+k)\log w\log n\)。

注意trie的空间请尽可能的开大，越大越好，只要不MLE，就往死里开。

一般开上\(20\sim30\)倍就差不多了

Code

例题9

P3690 【模板】Link Cut Tree （动态树）

LCT，一种基于splay的数据结构，用来动态处理树的形态和连通性问题。

Code

例题10

P3203 [HNOI2010]弹飞绵羊

很巧妙的将一个奇怪的问题转化成了树上问题！

Code

例题11

P3377 【模板】左偏树（可并堆）

支持两个操作：合并两个小根堆，查询第\(x\)个数所在的堆的堆顶并将其删除。

首先是并查集的找父亲：

int getf(int x)
{
	if(f(x)==x) return x;
	return f(x)=getf(f(x));
}

左偏树的合并很像\(FHQ-Treap\)，因为他们都是基于堆的，比较关键字的优先级。

int merge(int x,int y)
{
	if(!x) return y;
	if(!y) return x;
	if(v(x)>v(y)||(v(x)==v(y)&&x>y)) swap(x,y);//let xdist(ls(x))) swap(ls(x),rs(x));//liftist heap
	f(ls(x))=f(rs(x))=f(x)=x;
	if(!rs(x)) dist(x)=0;
	else dist(x)=dist(rs(x))+1;
	return x;
}

pop：合并根节点的左右子树。

void pop(int x)
{
	v(x)=-1;
	f(ls(x))=ls(x);
	f(rs(x))=rs(x);
	f(x)=merge(ls(x),rs(x));
}

与\(FHQ-Treap\)相比，可以\(O(1)\)查询最小值，代码量少，但是要多维护一个\(dist\)，其他就没有什么优点了吧……

Code