基础数据结构学习笔记

Vanilla_chan · 2021-04-02 09:25:39 · 个人记录

基础数据结构学习笔记

来自\color{Gray}\texttt{SharpnessV}的省选复习计划中的基础数据结构。

应某\color{gray}sto毒瘤\color{gray}orz的要求，笔记顺序按照题单中的题目顺序编排。

基础数据结构，顾名思义，就是比较简单的数据结构了。

先列出会用到的基础数据结构/算法/思想吧：

• 并查集1,3
• 队列2
• 线段树3,7,12,13
• 分块3,9
• 前缀和4
• ST表4
• 二叉堆4
• 树状数组5,6
• 根号分治8,9
• 平衡树10,11
• 树链剖分12,13

下面开始讲例题。

例题1

P1955 [NOI2015] 程序自动分析

有一堆类似于x_i=x_j和x_i\neq x_j的n(n\le10^6)个条件，询问这些条件能否同时满足。

并查集可以维护x_i=x_j但是不能维护x_i\neq x_j，因为不等于不具有传递性。

考虑离线，然后对于所有的x_i=x_j进行merge(i,j)；再对于所有的x_i\neq x+j查询他们是否不在一个集合内。

注意i,j\le10^9，所以要离散化。

Code

例题2

P2827 [NOIP2016 提高组] 蚯蚓

一共有n只蚯蚓，每只蚯蚓有一个长度，并且蚯蚓会按每年q厘米的速度增长。现在每年选择一只最长的蚯蚓，将其按p的比例切成两半，被切的的蚯蚓这一年不能增长，问每年被切的蚯蚓的长度和m年后所有蚯蚓的长度（据题意只需输出部分结果）

看到这题首先想到的是使用堆来做（因为，切蚯蚓符合堆的查询极值、插入和删除）。但考虑到数据的范围(1\le n\le10^5,0\le m\le 7\times 10^6)，由于使用堆的时间复杂度为\rm O(m\times \log n)，其结果必然会导致超时，所以只有另辟蹊径。

再仔细观察，发现每年切最长的一只蚯蚓，说明切过的蚯蚓长度具有单调性，即先切的蚯蚓的左段一定大于等于后切蚯蚓的左段，先切蚯蚓的右段一定大于等于后切蚯蚓的右段。

以下为证明过程：为方便，设两只蚯蚓长度为a，b，切后的长度分别是a_1,a_2,b_1,b_2.

因此我们可以想到这题可以使用普通队列来做，使复杂度降至\rm O(m)。

使用3个队列分别保存没被切过的蚯蚓，被切过的蚯蚓左段，和被切过的蚯蚓右段。

每次取出3个队列中最长的一只蚯蚓，将其切断都分别放入后两个数组，依此类推循环m次即可求出结果。

还需要考虑蚯蚓的增长长度问题，由于每次除了被切的蚯蚓，其他所有的蚯蚓都在增长，所以只需要再从队列中取元素的时候加上(i-1)\times q，放回时减去i\times q的长度（因为被切的蚯蚓这年不增长，所以多减q厘米，具体实现参见程序）。

Code

例题3

P5012 水の数列

给你一个长度为n(n\le10^6)的数列，有T(T\le 10^3)组询问，每一组询问查询区间[l,r]，请选择一个x，将所有\le x的数标记后得到的段数\in[l,r]，得分为每一段连续标记的区间的长度的平方和除以x，最大化得分。

显然这不就是莫队直接过嘛

这还不就是莫队，卡卡常再来个指令集

初始化是就先将[1,n]中第二次出现的数的贡献+1。

最后问的是[l,r]，那么就用树状数组维护前缀和的贡献，差分出区间的贡献即可。

Code

例题7

P4198 楼房重建

在一个平面内，询问所有的高度大于0的点与(0,0)的连线没有与之前的线段相交的楼房.带修。

很好的线段树题目。

这道题告诉了我，线段树不是只是用来做带修区间和的。

既然是共用了原点(0,0)，所以会影响答案的量就是线段的斜率。

如果说用线段树的话，大部分地方都非常显然，需要维护区间内有多少个楼房是可见的sum，区间最高的斜率k……但是唯独不知道如何合并两个区间。

首先，在左边的那一个区间的sum是一定可以直接被看到的，可以直接加入父区间的sum。

而右边的楼房中，只有斜率\ge 左区间的k的楼房才能被看到。为了计算右区间的贡献，我们用一个函数\rm calc(k,p)表示计算当左边有个线段的斜率是k时，线段树上的节点p所代表的区间中有多少楼房可以被看到（有贡献）。

在\rm calc(k,p)中我们继续递归计算。

• 若l_p=r_p，则只要k<k_p则return 1，否则return 0.
• 将区间分成两部分，设为L,R:
  1. 若\rm k< k_L，那么R中的贡献是保持不变的，只需要再递归计算L的贡献。
  2. 若\rm k\ge k_L，那么左区间的贡献为0，只需要继续计算R的贡献。

需要注意的是，对于情况1，R的贡献不是R_{sum}，而是Fa_{sum}-L_{sum}。因为R_{sum}的定义是R这个区间（在这个区间之前没有任何的阻碍物的情况下）有多少房屋能够被看到。

int calc(double k,int p)
{
    if(l(p)==r(p)) return k<k(p);
    int mid=l(p)+r(p)>>1;
    if(k<k(p<<1)) return calc(k,p<<1)+sum(p)-sum(p<<1);
    return calc(k,p<<1|1);
}

Code

例题8

P3396 哈希冲突

先想两种极端的做法

• 对于每个询问，暴力计算k,k+p,k+2\times p\dots的value之和。
• 预处理出ans[p][k]表示在\bmod p的意义下，余数为k的value之和。

第一种方法时间\rm O(n^2)，空间\rm O(1)；第二种方法时间\rm O(1)，空间O(n^2)。

考虑根号分治。

对于p\le \sqrt n，我们预处理，保存在数组ans[p][k]中。空间\rm O(\sqrt n\times\sqrt n)=\rm O(n)，时间上预处理\rm O(n\sqrt n)，修改\rm O(\sqrt n)，查询\rm O(1).

对于p>\sqrt n，我们不预处理，每一次询问暴力统计。每次统计的数量不会超过\dfrac np\le \sqrt n.

Code

例题9

区间众数。

普通版

前置知识：基本的分块，求众数。

本文将以从洛谷 P4168 [Violet]蒲公英的转换视角来解决这道题。蒲公英这道题不仅数据范围友好，题目背景也不错。

[P4168 [Violet]蒲公英](P4168 [Violet]蒲公英)

不妨可以去看看我的题解，顺便点个赞awa

给你一个长为 n 的序列 a，m 次询问，每次查询一个区间的众数的出现次数，强制在线。

以下默认块大小为\sqrt n.

首先离散化。

预处理出从第i块到第j块中的众数zs_{i,j}。可以枚举i,枚举j，再枚举块内元素开一个桶统计。时间复杂度O(n\sqrt{n})，空间复杂度O(n)+O(\sqrt n\times \sqrt n)=O(n)。

预处理出第1块到第i块这个区间[1,i]中数字x出现的次数cnt_{i,x}。可以枚举i后，先将(\forall x)cnt_{i-1,x}拷贝到cnt_{i,x}，再统计当前块i。时间复杂度O(\sqrt n\times (n+\sqrt n))=O(n\sqrt n)，空间复杂度O(n\sqrt n)。

对于每一个询问(l,r)，讨论其是否在一个块内。若是同块，就使用桶暴力统计。若不在一个块内，则将其拆为两个散块和一个整块。

首先答案ans=zs_{i,j}，再向两边拓展，看看散块内的数x是否可能成为比ans出现次数更大的数。具体的，整块中x出现的次数可以用之前预处理出的cnt_{j,x}-cnt_{i-1,x}这种形式表示。散块中的x使用桶来统计即可。

询问的时间复杂度为O(\sqrt n+2\times \sqrt n)=O(\sqrt n)。

Code

加强版

蒲公英的数据范围十分友好：n\le 4\times 10^4,m\le 10^5。所以我们完全能够开下cnt_{s,n}。

但是P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III的数据范围就不那么友好了：n,m\le 5\times 10^5。

这两道题有许多的共同点：区间众数，无修改，要离散化，数据范围看上去是根号做法的。

但是也有一些不同点：无法预处理前缀块的桶（因为空间开不下），求的是众数出现的次数而非众数是谁（其实差不多，但是求出现次数的话需要处理的信息可以少了点）

无法开桶，那么可以用另一种方式表达这个桶吗？可以的。

首先离散化，预处理zs_{i,j}就不必多费阐述了吧。

使用n个vector中存放下标，vector_{x,i}表示数x第i次出现的下标。由于是vector，所以总空间依然是O(n)的。

再记p_i表示i这位上的数x在其vector_{x}中在第几位。

显然预处理这个的时间复杂度是O(n)的。

对于每个询问，我们还是类似于上面的那样，同块暴力统计即可；

否则依然将其拆分。首先ans=zs_{i,j}（注意，这里的zs_{i,j}不再是[i,j]块内的众数，而是其出现的次数），在考虑两边的散块中，数x的出现次数能否更新ans。

比如，现在正在考虑在左侧散块的下标为i的数x能否更新ans。p_i是i之前有多少个x，那么至少要存在第ans+p_i个x，且ans+p_i要在[l,r]的数据范围以内，答案就可以被更新，ans++。

若在右侧则同理。

Code

小节

分块模板题的训练就到此完结了。

但是分块的玄学美妙优雅暴力之处不仅仅于此。

比如根号平衡等。

比如P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III这道题其实还可以二分查找最后一个\le r的数，使得总时间复杂度变为O(NT+MN/T*\log t)\stackrel{T=\sqrt{N\log N}}{\longrightarrow}O(N\sqrt{N\log N})[^1]级别的。

大概是因为这只是Ynoi的模拟赛吧，就没有那么卡时间。

但是遇到毒瘤题，根号平衡是一种很重要的卡常方法。

以后遇到了卡常分块的话可以记录一下。

[^1]: 算法竞赛进阶指南 0x44

例题10

P2042 [NOI2005] 维护数列

请写一个程序，要求维护一个数列，支持以下6种操作：

1. 在第pos个数字后面插入tot个数字
2. 从第pos个数字开始删除tot个数字
3. 从第pos个数字开始覆盖tot个数字为c
4. 从第pos个数字开始的tot个数字翻转
5. 区间和
6. 最大子段和

P5066 [Ynoi2014] 人人本着正义之名

对一个01序列进行以下m个操作：

1. 区间覆盖为0
2. 区间覆盖为1
3. 将区间[l,r-1]中的数a_i同时变为a_i与a_{i+1}按位或的值
4. 将区间[l+1,r]中的数a_i同时变为a_i与a_{i-1}按位或的值
5. 将区间[l,r-1]中的数a_i同时变为a_i与a_{i+1}按位与的值
6. 将区间[l+1,r]中的数a_i同时变为a_i与a_{i-1}按位与的值
7. 查询区间和

强制在线。