2020 年电子科技大学 ICPC 暑假前集训数据结构专题一句话题解

Posted on 2020-05-09 In OI/ICPC

一年一度写专题题解，但是因为电脑没带回来不能更新博客了（悲），所以就用 Lutece 的 blog 代替了。

但是今年题太多就不写完整题解了（懒），有原题的话会给出原题链接。

A - 红魔族首屈一指の恶魔使

关键词：括号匹配，栈。

根本不用开栈，就直接维护一些变量加加减减就好了。大概注意一下 n 为非负整数就好了。

说人话：n = 0。

时间复杂度：𝒪(n)，空间复杂度：𝒪(1)。

Problem setter：whfym

代码见这里

B - 雪菜的新家

关键词：并查集。

实际上是一张 DAG 图，对于 a_i 连向 i 即可，最后问强连通分量的个数。可以利用并查集完成操作。

能想到的图论方法：拓扑序，Tarjan 求 SCC。

时间复杂度：𝒪(nlogn) 或 𝒪(nα(n))，空间复杂度：𝒪(n)。

Problem setter：H_cheung

代码见这里

C - 我，不是说了能力要平均值么

关键词：逆序对，数学。

令 A_i = S_i − ki，则求在 0 ≤ i < j ≤ n 中，A_i 的逆序对数即可。概率输出即为逆序对数与的比值。

注意数据类型的使用。

时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(n)。

Problem setter：HeRaNO

~~上概率论课路上想到的，但是和 AtCoder Regular Contest 075 C. 差不多，悲伤的故事……~~

~~当你以为出了一道好题的时候，基本别人都已经出过了。~~

代码见这里

D - 利姆露的魔法序列

关键词：括号匹配，线段树。

来自 Codeforces Round #603 (Div. 2) E.，注意原题在最左边时指针不能再向左端移动，本题可以。于是先要开一个 n 的缓冲区以支持这个操作。

时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(n)。

Problem setter：louroborus

代码见这里

E - 哪个男孩不想挖最多的矿呢

关键词：二分答案，二维 ST 表。

首先二分这个边长，然后枚举中心点，做整个范围求 gcd ，这里就可以用二维 ST 表进行处理了。

二分答案中判断函数可以直接返回满足这个边长的正方形有多少个，就可以简单处理第二问答案了。

注意到正方形性质，这个二维 ST 表就可以省掉一个 log 的维度了。

时间复杂度：𝒪(n²log²n)，空间复杂度：𝒪(n²logn)。其中多的一个 log 来自求 gcd 。

请不要忽略一些看似很快就能求取的函数，如 gcd , x^k 等的时间复杂度，这可能会导致复杂度分析错误而被「卡常」。在下面的题与数学与几何专题我们将再次谈到。

然后被搜索爆过去了（毕竟是大概答案的复杂度），然后数据加强了。（没想到害真行）

Problem setter：__santongding

代码见这里

F - 赏金

关键词：平衡树，前缀和。

来自雅礼集训，LibreOJ #6047.。

时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(n)。

Problem setter：H_cheung

代码见这里

G - 红魔族首屈一指の鞋店老板之子

关键词：可并堆。

来自 USACO 2012 Dec. Gold T3.。

时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(n)。

Problem setter：whfym

代码见这里

H - 綾波的游戏 I

关键词：分块。

分块维护序列，记 f_i, j 为第 i 块内模为 j 的元素个数，区间修改维护块内增量即可。注意可能需要把查询和修改写成同一函数以避免常数问题。还需要注意负数的处理等。

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

~~这是 whfym 爷爷某天晚上在出题群糊的一道题~~

Problem setter：H_cheung

代码见这里

I - 利姆露与魔法元素

关键词：并查集，食物链。

因为只有删除操作，所以我们倒着做。先把并查集的最后状态处理出来，然后删除就相当于加入条件了。

对于关系处理，是 NOI 2001 的食物链一题，已经是超经典的处理方式了。

时间复杂度：𝒪(nlogn) 或 𝒪(nα(n))，空间复杂度：𝒪(n)。

Problem setter：louroborus

代码见这里

J - 百分之 99 的人竟然不知道两个数字之间还能这么算

关键词：点分治，Trie 树。

直接点分治求取答案，对于二进制异或，维护 01Trie 即可。

答案有前缀和性质，可统计为异或和小于等于 r 的答案数减去小于等于 l − 1 的答案数。假设当前要统计小于等于 k 的答案。按 k 的二进制在 Trie 树上统计即可。注意 k 可能小于 0。

时间复杂度：𝒪(nlognlogmax{a_n})，空间复杂度：𝒪(nlogmax{a_n})。

这里 Trie 树复杂度与点分治复杂度不同阶。

Problem setter：__santongding

代码见这里

K - 简单题

关键词：单调栈，贪心。

来自 Gym102433B，注意判断无解情况。

时间复杂度：𝒪(n)，空间复杂度：𝒪(n)。

Problem setter：HeRaNO

代码见这里

L - 红魔族首屈一指の大魔法师

关键词：LCT。

来自 SDOI 2008 洞穴探测。

类似动态图地，线段树分治+并查集可做。

时间复杂度：𝒪((n+m)logn)，空间复杂度：𝒪(n)。

Problem setter：whfym

代码见这里

M - 这个群里是就我不会机器学习了吗

关键词：k-D Tree，并查集。

板子题。想法来自 HDU 5809，但是原题还需要图论知识于是做了简化，然后简化地面目全非。

时间复杂度（平均）：𝒪(nlogn)，空间复杂度：𝒪(n)。

Problem setter：HeRaNO

代码见这里

N - 利姆露与魔法阵

关键词：树链剖分，线段树。

板子题。

时间复杂度：𝒪(mlog²n)，空间复杂度：𝒪(n)。

Problem setter：louroborus

代码见这里

O - 尤斯蒂娅的麦穗

关键词：线段树二分，分块。

分块可以过，板子题。

时间复杂度：𝒪(mlogn)，空间复杂度：𝒪(n)。

Problem setter：H_cheung

代码见这里

分块实现见这里

P - 我，不是说了能力要平均值么 · 改

关键词：线段树，数论。

打表可以发现循环节长度为 27，直接线段树维护合并即可。

想法来自 ZOJ 4009，也可以来自 CSP 2019 12 月 T5。

~~想搞成大型找规律现场但是想想还是做个人吧……~~

时间复杂度：𝒪(mklogn)，空间复杂度：𝒪(n)。其中 k = 27。

Problem setter：HeRaNO

代码见这里

Q - 自动 Treap 机

关键词：Segment Tree Beats!，思维。

来自 Codeforces Round #616 (Div. 1) E.，注意原题给出最终排列，但是本题是依次添加的。稍微改改就行了。

顺便要离散化。

时间复杂度：𝒪(nlog²n)，空间复杂度：𝒪(n)。

Problem setter：__santongding

代码见这里

R - 利姆露的魔法咒语库

关键词：可持久化线段树。

板子题，感觉有奇怪搞法。洛谷上也有板子其实。

时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(nlogn)。

Problem setter：louroborus

代码见这里

S - 鸽子与 808

关键词：Splay，二分，数学。

注意到这是基础的动态带权中位数，Splay 维护一下序列（区间加，区间翻转）就好，查询答案可以在 Splay 上二分或者二分套 Splay。

熊爷爷顺手一个 𝒪(mlogn) 把标程干了。

时间复杂度：𝒪(mlog²n)（标程）或 𝒪(mlogn)（最优），空间复杂度：𝒪(n)。

~~原来这道题是出给省选模拟赛的，但是没卖出去就留到这儿了。~~

~~甚至发现这道题原标程锅了……~~

Problem setter：HeRaNO

代码见这里

T - 红魔族首屈一指の族长之女

关键词：树上带修莫队。

来自 WC2013 糖果公园，不卡常哈。

时间复杂度：，空间复杂度：𝒪(nlogn)（来自 RMQLCA）。

Problem setter：whfym

代码见这里

U - 只要题目名字够长里面配图够多，即使题面写得再烂题解再毒瘤你也一定会写的吧！

关键词：差分，延时重构。

注意到维护合并类数据结构都需要一个 log 的时间，过不去，所以考虑对操作分块处理。处理下一块操作的时候重构当前三角数阵，块内操作记录修改，并 𝒪(1) 计算答案。

来自某 NOIP 模拟赛。

时间复杂度：𝒪(mn)，空间复杂度：𝒪(n²)。

注意复杂度分析。

Problem setter：HeRaNO

代码见这里

V - 一道普通的数据结构题

关键词：线段树上二分。

板子题。双倍快乐题。

时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(n)。

~~题面是我补的~~

Problem setter：Sugarii

代码见这里

W - 我，不是说了能力要平均值么 · 改二

关键词：线段树加等比数列，数学。

注意到 Fibonacci 数列还要模 10⁹ + 9，很容易想到搞二次剩余什么的。

注意到 Fibonacci 数列的通项公式

其中比较糟心的部分就是，如果没有这个无理数我们处理起来就很简单了。在模意义下有理数处理起来比较轻松。

下面介绍二次剩余，即我们想求出一个整数 x，使得满足

x² ≡ 5 (mod P)

具体解法是数论问题，结果是在 P = 10⁹ + 9 时，这个二次剩余方程有解（比较显然的是有解必有两解，因为模意义下区分不出负数），x₁ = 383008016, x₂ = 616991993，我们取其中一个即可，这里取 x = 383008016。

令

则

来点计算

令 A = a², B = b²，则

这样我们可以看出，每次区间加其实加了三个等比数列。

我们维护公比相同的等比数列，可以看出，只要维护首项的标记即可，算影响时利用等比公式求和即可（这里可以利用快速幂），因为公比均不为 1，所以不需要特别考虑。

注意运算均在模 10⁹ + 9 意义下进行，A, B 的取值可以根据 x = 383008016 自行计算（注意模意义下做除法的方式为乘以其逆元）。

但是某天在 UOJ 群水群的时候一位神仙提出这道题模数也是可以变成任意的，根据论文《Fibonacci 数列与 Lucas 数列的方幂和》，可以看出 Fibonacci 数列的平方和也是可以写成线性递推的

其中 {L_n} 是 Lucas 数列，L₁ = 1, L₂ = 3, L_n = L_n − 1 + L_n − 2 (n≥3)。

但是标记处理和计算影响时仍需要推导（但是目测不是很好处理标记）（目测不写这个就会变成 flag 并被这个 flag 杀了）。

UPD：Sugarii 写了任意模数的，不会的问他（我也没整明白）。

改编自 Codeforces Round #FF (Div. 1) C.。

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

注意到直接利用快速幂可能多一个 log P 的复杂度，导致常数较大，可能会被「卡常」。

Problem setter：HeRaNO

代码见这里

X - 路口

关键词：离线，树状数组。

考虑离线并离散化后利用扫描线求解，可以看出，答案可以拆成前缀和形式，这样我们统计上下边界的答案，利用前缀和即可在 𝒪(1) 的时间内回答。这里选取扫描线为一条平行于 x 轴的直线，当扫描到某一个 y 坐标时，先处理平行于 y 轴的线段的影响，如果是线段的起点（从下到上看），就给这个坐标位置加一，如果扫描线已经脱离这条线段，就给这个坐标位置减一（这里的统计思想同样类似前缀和，若处理不当会导致统计边界情况出错）。然后计算这条扫描线上每条平行于 x 轴的线段给答案带来的贡献，总体上看，是一个单点修改区间查询问题，利用树状数组便可快速求出。

改编自 LibreOJ #3249. 的 Checker。

时间复杂度：𝒪(nlogn+m)，空间复杂度：𝒪(n)。

Problem setter：HeRaNO

代码见这里

Y - 诶，我和你讲这瓜超休闲的

关键词：线段树，线性基。

来自 Codeforces Round #326 (Div. 1) E.。

时间复杂度：𝒪(mlognlog²max{a_n})，空间复杂度：𝒪(nlogmax{a_n})。

Problem setter：Vingying

代码见这里

Z - 綾波的游戏 II

关键词：ODT。

注意到区间推平操作很多，因此可以考虑 ODT，这里时间复杂度是对的，因为端点进出只 1 次。

时间复杂度：𝒪((n+m)logn)，空间复杂度：𝒪(n)。

Problem setter：H_cheung

代码见这里

分块代码见这里

Bonus

https://osu.ppy.sh/beatmapsets/<题面里出现的神奇数字> 有惊喜。（仅限部分题目中的部分数字 ^ ^）

~~Normal 全白金 SS 达成的同学将在数学与几何专题获得 0 分的优秀奖励。~~