2019 年电子科技大学 ACM-ICPC 暑假前集训数据结构专题解题报告

Posted on In

14/15/15

讲之前 14/15，之后补完了。

A. 方差

题目描述

维护一个数据结构，支持区间加法，区间乘法，区间置为同一个数，询问区间方差。

数据范围：。

题解

考虑方差公式：

对于区间内部，考虑用完全平方公式展开，后代入平均值，即：

要输出的答案为 ，即：

因此，我们需要维护的是区间平方和和区间和。因此考虑用线段树解决。

对于区间加法，设区间 整体加 ，那么区间和需加上 ，对于区间平方和的增量有如下推导：

那么增量即为 ，并且区间平方和的增量应在区间和增量处理之前处理完成。最后加标记加上 。

对于区间乘法，设区间 整体乘 ，那么区间和整体乘以 ，区间平方和整体乘以 ，乘标记乘以 。这部分是显而易见的。

对于区间置同一个数 ，可以看做区间乘以 ，再对相同区间加 。因此拆为两个操作即可完成。

对于询问，直接查询区间和与区间平方和即可。

就这样，我们可以在只打两个标记的情况下完成维护三个修改操作了。

时间复杂度 ，空间复杂度 。

代码见这里

B. 吞吐量

题目描述

对于一棵有边权的树，多次询问两点间路径权的最小值。

数据范围：。

题解

本题有一个显而易见的暴力做法，即每次从 走到 ，直接查询这个最小值，时间复杂度 。

考虑用倍增思想优化，预处理出每个点向上跳 步后的点和到这个点之间的路径权的最小值。然后每次查询的时候先将两个点调整至相同深度，然后同时向上跳，以求出最小值。

事实上，上面写的可以用一句话概括：LCA。

（当然还可以写 RMQ-LCA）

（其实我也不知道为啥我把 LCA 讲了出来……）

时间复杂度： 或 （RMQ-LCA）。空间复杂度：。

原题详见：

类似题目详见：

（当然上面那道题主要是 Kruskal 重构树……）

代码见这里

C. 人在地上走，锅从天上来

题目描述

原来一条线段均为白色，每次对一个区间染黑，问有多少个黑色区间。

数据范围：。

题解

对于区间染色问题，可以考虑用线段树方法实现。但是本题合并不满足区间可加性，因此需要增加维护的信息。

对于一个区间 ，维护 两点的颜色与区间内部黑色区间段数。合并的时候，只需要判断左区间的右端点和右区间的左端点是否同为黑色，如果都是黑色的话，大区间的答案为两小区间答案和减一，否则直接求和不需要减一。对于查询，直接取出最大的区间的答案即可。

需要注意的是，可能会有染色区间为一个点的情况，这时候需要维护单点。因此修改分为单点修改和区间修改即可。或者线段树区间写为左闭右闭即可。

对于 范围过大的问题，可以采用离散化的方式将其降到 的规模。

时间复杂度 ，空间复杂度 。

代码见这里

D. 密码

题目描述

对于一个数列，留下 个数，使得其相对位置不变并且表示的十六进制数值最大。

数据范围：。

题解

对于保留 个数，我们可以看做删除 个数。那么这就是一个经典的贪心问题，原题为：对于一个十进制大整数 ，从左到右依次删除 个数，使其剩下的数组合成的新数最小。本题将原问题的两个要求「删去」「最小」均反过来了。

对于保留 个数，即删去 个数，这个改变对于贪心并不大碍。

对于求最大值，原题采用的是最近下降点优先删除的策略，那么这里将其反过来，采用最近上升点优先删除的策略即可，我们可以用单调栈快速实现，并且代码十分简单。

时间复杂度 ，空间复杂度 。

代码见这里

E. 冬马和纱天下第一

题目描述

给出一个数列，问 中的数最少可以组成多少个严格上升的序列。

转化题意，因为可以数字重排，于是我们可以统计这个区间的数字出现次数，为了使严格上升的序列最少，我们需要把出现最多的数字安排进每一个对答案有贡献的序列里，如果出现次数最多的数字都被安排进贡献中，那么出现次数少的数字一定可以全部被安排完毕。因此答案即为出现次数最多的数字的出现次数，即区间众数的出现次数。

因此最终题意为：多次询问区间内数字出现最多的次数，强制在线。

数据范围：。

题解

对于在线求解区间众数问题，已经有成熟的 的分块方法。首先对序列分块，预处理出数字 在第 块的出现次数和第 块的答案。这一操作的复杂度为 。对于统计答案，零散部分暴力统计，整块直接调用预处理出的答案。查询的复杂度为 。

时间复杂度 ，空间复杂度 。

原题详见：BZOJ 2724. [Violet 6] 蒲公英

代码见这里

F. 我永远喜欢冬马和纱

题目描述

同 E 题，但是本题允许离线。

数据范围：。

题解

本题也可以像上一题一样分块求解，时间复杂度为 ，实际上复杂度并不在 1500ms 可接受的运行时间范围内。通过多次调参，加入时间戳减少清空数组的次数等方法卡常，发现数据是造得是真的好。对于第 31, 38, 41 组数据，可能都是通过卡到分块边界来实现的。网络上有一种 的方法，虽然多了一个 但是跑得挺快，但是不能通过第 51 组数据，猜测是通过减少区间内部数字种类实现的。

正确解法是采用莫队算法。需要统计一个区间内数字出现的次数和出现次数的次数，这些都可以在 的时间复杂度下维护，但是对于区间内数字出现次数的次数，可能是因为区间左右端点移动的连续性导致最大值每次只移动一位而不会移动多位，我在代码里写的是 while 循环，没有超出时间限制。

但是时限确实卡得有点紧……而且莫队跑得比带一个 加时间戳优化的要慢……

事实上，分块最大的问题在于空间上过不去，但是因为 OJ 对于空间限制有 Bug 并没有 MLE……

时间复杂度 ，空间复杂度 。

代码见这里

G. 线段树教做人

题目描述

维护一个数据结构，支持维护单点加，修改数列相邻两项差不小于 （ 给定），查询 的区间和。

数据范围：，并且 数列中元素只增不减。

题解

首先我口胡了一个差分，结果被 Decision 大爷暴过去了。详细过程见 Decision 大爷的题解。

我目测这个差分不是那么好差的，但是我还在线段树上维护六个东西的时候，Decision 大爷说「暴力」。

然后我线段树维护就地爆炸……

首先我们有两个数组 ，要维护 数组，使得 一直成立。当初想法是 Segment Tree Beats!，可以快速置区间内部为 ，但是看起来没啥用……

这个柿子看起来不好吃看，主要原因是左边一个 而右边是 ，为了处理这样的柿子，一个想法是把相同数列里的东西移到一遍，就是差分的思路，但是这里有个很巧妙的方法，即把 数组用前缀和的差来维护。

记 ，那么 ，代入上式，即 ，进一步移项得：。

令 ，于是要维护的是一个 的单调不减的序列。对于修改操作，每次对要修改的位置 加上对应的值 。因为要维护 的单调不减性质，于是需要找出最后一个小于 的位置 ，并将 之间的所有位置的值统一改为 ，需要注意的是， 是 的前缀和，是不变的。对于在线段树上查找最后一个小于某元素的位置，可以通过维护区间最小值来进行贪心，如果区间最小值大于等于 ，那么这段区间必无解，否则先查找右端区间，再查找左端区间，可以证明这样做的时间复杂度为 。

对于查询操作，我们查询 两个数组的区间和，将它们相加即为答案。

时间复杂度 ，空间复杂度 。

代码见这里

H. 拍照

题目描述

对于一个数列，求区间长度小于等于 的最大子区间和。

数据范围：。

题解

对于本题，有一个显而易见的动态规划解法。设 为 数列的前缀和，并记 ， 为以 为结尾，长度小于等于 的最大子区间和。那么有如下转移：

对于暴力转移，时间复杂度为 ，其中复杂度消耗在寻找最小值上。然而对于寻找最小值，我们可以利用线段树优化，将前缀和用线段树维护区间最小值即可。

时间复杂度 ，空间复杂度 。

注意边界，否则会 WA 在最后一个点上。

实际上，本题可以用单调队列优化求区间最小值的过程，时间复杂度可降至 。

代码见这里

I. 排名

题目描述

维护一个数据结构，支持动态插入，删除元素，并查询元素的排名。

数据范围：。

题解

本题的元素虽然不是一个整数，但是是全序关系，可以进行比较。

需要维护的操作是平衡树可以完成的，但是不能用 set，因为 set 查询元素排名是 的。因此考虑手写平衡树。Treap，Splay 都可以，这里选择 SBT 作为平衡树。

修改一个元素可以看做先删除原来的元素，进行修改后再插入进去。

时间复杂度 ，空间复杂度 。

代码见这里

J. 种海带

题目描述

求一个环上选择 个不相邻的元素之和的最大值。

数据范围：。

题解

对于 ，无解。

对于有解的情况，如果不考虑相邻，可以考虑用堆贪心，但是需要考虑不相邻这一限制条件。可以发现，要么是一个最大值计入对答案的贡献，要么是最大值两边的元素和计入对答案的贡献。即最大值两边元素和大于最大值或小于等于最大值。这样我们就需要撤销之前的贪心操作，因此在维护时，记录一个点之前的点和之后的点，每次取最大值时将其前驱后继删除，并把这点权值改为两边权值和减去原该点权值，再把它插入堆中。这样如果该点被再次查到，那么就是需要将最大值两端计入贡献中的情况，并且可以保证不相邻。

时间复杂度 ，空间复杂度 。

原题详见：Luogu P1792. [国家集训队]种树

代码见这里

K. 对答案

题目描述

给出一些连续子串和的奇偶性，判断是否能满足要求。

数据范围：。

题解

本题可以将子串分为两类，子串和为奇数或偶数。考虑到子串和不方便维护，我们可以维护前缀和，子串和即为两个前缀和之差，即 。

我们可以讨论 与 的奇偶性。如果 为奇数，那么 与 的奇偶性不同，如果 为偶数，那么 与 奇偶性相同。于是维护两个并查集即可。对于奇偶性不同的元素在并查集之间连边，对于奇偶性相同的元素在两并查集内部连边。在查询时，需要先查询是否已经能判断出奇偶性，如果输入与已经给定的输入判断相反，则输出错误信息，如果一直到最后都能满足条件，则输出 ORZQHQH。

时间复杂度 （只路径压缩）或 （按秩合并且路径压缩），空间复杂度 。

原题来自：POJ 1733. Parity Game（为原题弱化）

代码见这里

L. 我的题面最简单，快来做！

题目描述

维护一个数据结构，支持区间加两段等差数列（组合起来为山峰形），求区间最长等差数列长度。

数据范围：。

题解

对于区间求最长等差数列长度，可以维护这个数列的一阶差分数组，转化为区间最长相同数字的长度，也可转化为二阶差分维护区间最长 的长度。这里考虑维护一阶差分数组。对于区间加等差数列，通过计算可知，若区间加等差数列 ，则差分数组 需加上 ， 区间加 ， 区间加 ， 位置加 。

对于维护最长相同数字长度，这个可以如同 C 题一样维护区间左右端点数字，区间左起最长连续数字长度，区间右起最长连续长度，区间内数字是否均相同和区间内部答案。通过考虑左区间的右端点和右区间的左端点即可合并答案。

线段树维护不容易合并的东西一般都需要维护左右端点信息以及类似信息，如同 SPOJ GSS 系列题一样。

虽然二阶差分可以做到只进行单点修改来完成操作，但是理论上推的是对的，但是实际上 WA on test 1……

然后就是本题重点不用 LaTeX 导致 WA 20 多次……（眼睛不需要可以捐给需要的人）

（反正这里是熊猫头，下面是脏话）

UPD：Gaw4Gura 大哥用二阶差分过了，在这里。我也不知道我二阶挂哪儿了，估计是合并答案错了……

时间复杂度 ，空间复杂度 。

代码见这里

M. My description is the most 単純な one,come on!

题目描述

给定一个树，树的节点非红即蓝，初始只有 号点为红色，其余点均为蓝色。要求支持将一个点改为红色，查询一个点到最近红点的距离。

数据范围：。

题解

很显然的一个想法是 LCT，因为这棵树是动态的……但是不会 LCT 作罢。

考虑利用动态树分治来进行求解，我们保存树分治时所有求出的重心，可以建立一棵深度不超过 的点分树。考虑点分治的过程，其实相当于不断倍增，求比自己大一倍的块之内的红点到他的最小距离，为块内距离的最小值与以重心为根的块间距离的最小值。因此我们对每个重心节点都用堆维护与其最近的红点即到其距离。查询时，查询该点到支配该点的每个重心维护的最近红点距离，取最小值即可。

本题中查询树上距离为基本操作，普通的倍增求距离会导致复杂度过高而超出时间限制，因此需采用 RMQ-LCA 将询问两点间距离的复杂度优化至 ，预处理时间不变，为 。

对于修改操作，单次时间复杂度为 ，对于查询操作，单次时间复杂度为 。因此，总时间复杂度为 ，空间复杂度 。

原题详见：SPOJ QTREE5

代码见这里

N. 数理统计

题目描述

维护一个数据结构，支持区间加法，查询区间和，区间极差。

数据范围：。

题解

对于本题，可以直接利用线段树解决。维护区间和，区间最大值和区间最小值即可。易知上述三个维护项均具有区间可加性，区间加法也可以利用打标记降低复杂度。

时间复杂度 ，空间复杂度 。

代码见这里

O. 战争

题目描述

维护一个数据结构，支持插入一个数，删除一个数，查询 对这些数异或的最大值与最小值。

数据范围：。

题解

因为异或运算只与二进制本位有关，不会向下一位进位，因此可以分开考虑其对答案的贡献。

事实上，对于本题有经典的 Trie 树方法维护。把一个数的二进制当做字符串插入 Trie 树中，插入删除操作同 Trie 树操作，询问时，每次贪心地维护答案即可。

时间复杂度 ，空间复杂度 。

代码见这里