CF3000的数据结构题做题记录-1
CF464E. The Classic Problem
肯定还是跑最短路,假设比较的复杂度是 \(O(\alpha)\),相加的复杂度是 \(O(\beta)\),那么我们直接使用 dijkstra 的复杂度是 \(O(\alpha(n+m)\log n+\beta m)\) 的。
考虑直接维护高精度二进制时 \(\alpha=\beta=n\),则复杂度是 \(O(n^2\log n)\) 的,显然无法通过。因为每一条边的边权的二进制只有一位,那么加法可以看作一段赋值为 \(0\) 后下一位变为 \(1\),可以考虑主席树维护这个内容。
比较的时候可以维护每一段的哈希值,然后用线段树二分找到第一位不同的值后比较,复杂度是 \(O(\log n)\) 的。相加的时候先线段树二分找出需要赋值为 \(0\) 的段,然后再单点修改,两部分复杂度都是 \(O(\log n)\)。综合下来,总复杂度是 \(O(n\log^2 n)\) 的,可以通过。
CF526F. Pudding Monsters
先记第 \(i\) 行的怪兽的位置为 \(p_i\),那么答案就是满足 \(p_{[l,r]}\) 排序后连续的区间 \([l,r]\) 的个数,这个条件当且仅当区间的 \(\max-\min-\text{cnt}+1=0\),其中 \(\max\) 是最大值,\(\min\) 是最小值,\(\text{cnt}\) 是区间不同的数的个数。
考虑扫描线,显然每次会有若干个区间的的 \(\max\) 更新,若干个区间的 \(\min\) 更新,若干个区间的 \(\text{cnt}\) 更新。显然维护前两个内容可以用单调栈做到均摊 \(O(n\log n)\);而最后一个内容可以记录上一次这个数出现的位置,复杂度也是 \(O(n\log n)\) 的。因此总复杂度是 \(O(n\log n)\)。
CF603E. Pastoral Oddities
首先利用人类智慧得到结论:存在合法边集当且仅当所有联通块大小均为偶数。充分性和必要性都显然好证。
然后考虑无修改的情况:联通块大小均为偶数时,添加边后依然满足条件。所以按边权从小到大排序,有用的边一定是一个前缀。因此答案序列也是单调不增的,可以考虑整体二分求解单调序列。
我们可以用可撤销并查集维护联通块,令 \(\text{Solve}(l,r,L,R)\) 表示 \(ans_{[L,R]}\) 的值在 \([l,r]\) 中,考虑如何求得 \(ans_{mid}\) 的值:最为朴素的做法就是将时间 \(\le mid\) 的边按照权值从小到大加入到并查集中,第一个联通块大小均为偶数的时刻即为 \(ans_{mid}\)。然而此时我们无法用之前求得的内容帮助求解,我们依然需要遍历所有边。考虑换一种思路,我们可以每一次操作完后不清空,然后撤销一些边的贡献,让这次剩下的边对递归求解的内容来讲有用。我们事先保证在处理 \(\text{Solve}(l,r,L,R)\) 时,权值 \(<l\) 并且时间 \(<L\) 的边已经全部加入并查集中,接下来对答案有贡献的边分成两部分:
- 时间 \(\le mid\) 并且权值 \(<l\) 的边。这些边显然不影响答案,先直接加入这些边。
- 时间 \(\le mid\) 并且权值 \(\in[l,r]\) 的边。按顺序加入这些边,直到图合法为止。
求出 \(ans_{mid}=m\) 后,发现接下来应当调用 \(\text{Solve}(l,m,mid+1,R),\text{Solve}(m,r,L,mid-1)\),对于第一个函数的调用,显然只需要保留 \(1\) 中的边,于是撤回所有 \(2\) 的贡献即可;接着撤回 \(1\) 的贡献,单独加入递归需要的边集后求解即可。复杂度是 \(O(m\log^2n)\) 的。
CF1446D2. Frequency Problem (Hard Version)
考虑根号分治,对于最大出现次数 \(\le\sqrt{n}\) 的序列,我们显然可以枚举最大出现次数后用双指针维护出最长的合法区间,这样的复杂度是 \(O(n\sqrt{n})\) 的。
而对于最大出现次数 \(>\sqrt{n}\) 的序列,考虑其中的两个出现次数最多的元素一定是在整个序列中出现次数 \(>\sqrt{n}\) 的数,而这样的数最多有 \(\sqrt{n}\) 个。接下来我们先证明一个引理:最优解的众数中一定包含全局众数。这个不难用反证法证明,即如果不包含全局众数,那么可以尝试拓展边界使得全局众数成为当前区间的众数,容易发现这可以实现,并且这个区间比之前不包含全局众数的区间更优。那么我们可以枚举另一种数,如果我们确定了哪两个数出现次数最多,将一种视为 \(-1\),另一种视为 \(1\),其余视为 \(0\),则问题转化为找出最长的和为 \(0\) 的区间,利用前缀和可以做到 \(O(n)\) 单次求解,总复杂度是 \(O(n\sqrt{n})\) 的。虽然我们找出的区间中可能存在另一个数的长度更长,但这说明选择这个数时我们的答案要更优,证明和上面的过程类似,于是正确性没有问题。
CF150E. Freezing with Style
我们考虑二分,判断是否存在中位数比当前值大的合法路径。对于二分出的 \(x\),将所有 \(<x\) 的边视作 \(-1\),\(\ge x\) 的边视作 \(1\),题目相当于询问是否存在长度在 \([L,R]\) 之间的边权和 \(\ge 0\) 的路径。
考虑长链剖分,先让长链上的点编号连续,那么 \(\text{dfn}_u+k\) 可以表示以 \(u\) 为根的长度为 \(k+1\) 的路径的边权最大值。对于所有点,更新自己所在的长链后,先判断在自己的长链上是否有符合条件的路径,显然有一段区间的长度是符合要求的;然后枚举轻儿子和路径上轻儿子的路径所占的长度,此时路径在当前点的子树上所占长度同样是一个区间;最后将轻儿子的所有路径加入到当前点的子树。因此我们需要区间修改用于更新长链,单点修改用于加入路径,区间查询用来判断是否有解,使用线段树即可做到 \(O(n\log n)\)。加上外部的二分,总复杂度为 \(O(n\log^2n)\)。
CF997E. Good Subsegments
这题是【CF526F. Pudding Monsters】的加强版,然而思路还是一样的,问题在如何统计答案。将问题离线后扫描线,只需要多维护一个历史最小值个数:我们用一个标记表示这个区间的最小值被贡献了多少次,然后先判断左右区间的最小值是否等于当前区间的最小值后正常下放即可,复杂度依然是 \(O(n\log n)\) 的。
CF319E. Ping-Pong
我们发现相交但不包含的线段显然可以相互到达,这些线段显然可以用并查集简单合并。唯一问题是包含关系的线段只能从里面向外面走,我们发现这其实问题不大,因为我们的方向是确定的,永远从内向外走。
于是我们可以维护所有连通块的能到达的范围 \([L,R]\),显然所有的范围要么包含,要么无交,否则我们会将它们合并成一个连通块。现在考虑判断 \(a\) 能否到达 \(b\),当 \(a\) 和 \(b\) 在同一个连通块内时显然可以到达,而当 \(a\) 的连通块被 \(b\) 的连通块完全包含时,显然 \(a\) 也可以到达 \(b\)。这样就可以 \(O(1)\) 判断了。
问题在于如何快速将所有相交的线段但不包含的线段合并。发现题目中给出的性质,满足了如果新给出的线段的某一个端点在原线段中,那么他们一定相交而不包含,只需要检查当前的连通块有哪些包含了这个新线段的两个端点后合并即可,可以用线段树做到 \(O(n\log n)\)。
CF696E. ...Wait for it...
考虑我们没有必要直接求出前 \(k\) 小:因为我们每次前 \(k\) 小的点都会被删除,那么每个点只会被删一次,因此我们寻找 \(k\) 次最小值是可以的,只需要判断路径上是否没有点然后提前退出。
考虑子树加和路径最小值两个操作,显然可以用树剖和线段树做到 \(O(n\log^2 n)\),因为每个点上显然只有编号最小的点有可能被选中,因此用一个 set
维护每个点上的最小编号即可,单次删除一个点后单独更新这个点的最小编号和在线段树上的贡献即可。
CF1163F. Indecisive Taxi Fee
观察不同的边对答案不同的贡献,我们发现:不在最短路上的边改动后,答案为原最短路和包含这条边的最短路替换边权取最小值;在最短路上的边改动后,答案为原最短路替换边权和不包含这条边的原最短路。注意到原最短路、原最短路替换边权是容易的,接下来考虑如何求解其他的内容。
对于包含某条边的最短路,对于边 \((u,v)\) 容易想到其路径应当为 \(s\to u\to v\to t\) 或 \(s\to v\to u\to t\),不难看出我们只关心 \(s\to u+v\to t\) 和 \(s\to v+u\to t\) 的值,因此可以分别从 \(s,t\) 开始跑一遍最短路,这样可以 \(O(1)\) 求出经过边 \((u,v)\) 的最短路,替换边权是容易的。
对于最短路上不包含某条边的最短路,可以考虑到其他每一条边的最短路总是通过一段最短路上的前缀 + 一段非最短路 + 一段最短路上的后缀得到,那么看出来这条路径不包括最短路上的某些边,可以借由这一点进行操作。更具体的,对于非最短路的一条边,我们求出经过其的最短路上前缀和后缀的信息,即在哪个位置路径开始分离,记为 \(L,R\),那么这两点之间的所有边都有这条路径的贡献,区间取 \(\min\) 即可。这个可以用线段树实现,复杂度是 \(O(\log n)\) 的。
综上,我们可以在 \(O((n+m)\log n+q)\) 的复杂度内解决这道题。
CF436F. Banners
考虑因为先判断 \(b_i\) 和 \(c\) 的大小关系,将所有用户按照 \(b_i\) 先从小到大排序,那么选择免费版的用户一定是一个后缀。在剩下的前缀中,假设有 \(t_p\) 个用户满足 \(a_i\ge t_p\),当我们选择 \(p\) 时将会获得 \(t_pp\) 的收益。那么当 \(c\) 确定时我们要做的就是找到 \(t_pp\) 的最大值和此时的 \(p\)。
考虑从小到大枚举 \(c\) 的过程中,有越来越多的前缀不会选择免费版,一个用户不选择免费版将给所有 \(p\le a_i\) 的 \(t_p\) 增加 \(1\) 的贡献。考虑我们要维护若干个 \(kx\) 的最大值,并且会给某个区间的 \(x\) 加 \(1\),和 KTT 所维护的内容是相同的,于是可以直接使用 KTT 做到 \(O(n\log ^2 n)\) 的复杂度。
CF793F. Julia the snail
因为不能超过 \(y\) 的这一个限制,我们可以想到枚举最大上限 \(y\),只有枚举到 \(r\) 时,所有从 \(l\) 到 \(r\) 的绳子才存在贡献。考虑对所有询问离线扫描线,对每一个 \(y\) 维护它的下限是 \(x\) 是能到达的最大高度。考虑加入一根从 \(l\) 到 \(r\) 的绳子时,我们只会更新所有能到达 \(l\) 的位置,即 \(x\le l\),且它们到达的最高高度 \(\ge l\)。那么就是将一段区间上 \(\ge l\) 的值全部改成 \(r\)(显然没有超过 \(r\) 的值),这可以用吉司机线段树简单做到 \(O(n\log n)\)。
虽然这里的操作和普通吉司机线段树的操作略有差异,但是在同时修改次大值和最大值时,我们总是会将次大值和最大值变成一样的,因此复杂度分析是一致的。
CF1178G. The Awesomest Vertex
考虑讨论 \(\sum a_i\) 的正负,显然如果在该取正的时候取负,或该取负的时候取正一定不优,因此我们考虑分别维护 \(-|\sum b_i|(\sum a_i),|\sum b_i|(\sum a_i)\) 的最大值。
现在考虑单点的 \(a_i\) 加上 \(x\) 相当于一个子树的 \(\sum a_i\) 加上 \(x\),那么考虑上面两个贡献都是 \(kx\) 的形式,并且 \(k\) 不变而 \(x\) 要进行区间加正数,因此使用 KTT 即可快速维护。对于查询来讲就是区间查询最大值,依旧可以用 KTT 维护。总复杂度是 \(O(n\log^2 n)\) 的。
CF773E. Blog Post Rating
不难看出将 \(a\) 从小到大排总是不劣,这个结论可以用邻项交换法简单证明。考虑排序后 \(a\) 的第 \(i\) 项为 \(a_i\),我们发现 \(F\) 总是先下降一段,然后单调不降。
考虑找到这两段的分界点处 \(F\) 的值,假设 \(\le F\) 的数有 \(p\) 个,拐点处一定满足 \(-p=F\)。并且因为 \(F\) 递增时 \(-p\) 一定递减,因此 \(-p\le F\) 具有单调性,找到第一个满足条件的 \(F\) 即为拐点。
考虑在拐点后,对于每一个 \(a_i\),我们有 \(F\leftarrow\min(F+1,a_i)\),将式子拆开,可以得到答案是 \(\min(a_n,a_{n-1}+1,\cdots,a_{p+1}+n-p-1,F+n-p)\)。将 \(n\) 提出来,维护 \(F-p\) 的最小值,其中 \(p\) 是 \(\le F\) 的数的个数。
上面的过程可以用线段树实现,找拐点的过程可以用线段树二分做到 \(O(\log n)\),而找最小值和更新也可以在线段树上区间操作做到 \(O(\log n)\)。总复杂度是 \(O(n\log n)\) 的。
CF331D3. Escaping on Beaveractor
因为在走到一个有向线段上的点后后面的路径都是确定的,所以我们可以考虑倍增:设 \(f_{(x,y),i}\) 表示从点 \((x,y)\) 出发走 \(2^i\) 步后所在的格子。这样显然只需要先考虑从起点出发走到的第一个线段,之后用倍增数组即可做到单次 \(O(\log V)\) 查询。然而这样预处理的复杂度是 \(O(b^2\log V)\),只能通过前两档数据。
考虑我们的路线实际上只和给出的有向线段有关,因为我们总是从一个线段走到另一个线段。那么可以设 \(f_{x,i}\) 表示从线段 \(i\) 的结束位置出发,走到路径上的第 \(2^i\) 条线段的编号,\(g_{x,i}\) 表示走到 \(f_{x,i}\) 的结束位置时走过的距离。那么我们依旧可以用倍增快速求出 \(t\) 足够我们走到哪一个线段。剩下的时间有几种可能:
- 从当前线段的结束位置走不到下一条线段。
- 从当前线段的结束位置可以走到下一条线段。
我们计算出从当前线段走到下一条线段的时间。如果时间足够,就从下一条线段的结束位置倒推,否则从这条线段的结束位置直接计算即可。上面的过程可以先忽略边界,在最后将坐标改到边界内。
考虑如何预处理出 \(f_{x,0}\):对四个方向分别扫描线一遍,每次新加入的线段可以覆盖一个区间,对应方向的线段能够到达的就是最后一个覆盖某一个位置的线段,这个可以用颜色段均摊做到 \(O(n\log n)\)。对于查询,我们可以考虑将其视作长度为 \(0\) 的有向线段,并且这些线段只查询,不做贡献。
预处理和查询的复杂度都是单老哥。总体的复杂度是 \(O(n\log V)\) 的。
CF185E. Soap Time! - 2
考虑先二分答案:对于一个距离 \(d\),每个人都有一个能到达的范围 \(B_i\)。这个 \(B_i\) 是由 \(i\) 的起始点出发走 \(d\) 步和所有地铁站出发走 \(d-D_i\) 步能到达的所有点组成的(其中 \(D_i\) 是 \(i\) 的起始点距最近的地铁站的距离),也就是说 \(B_i\) 是若干个菱形的并。菱形不是很好处理,因此我们将曼哈顿距离转成切比雪夫距离,这样 \(B_i\) 就是若干个正方形的并,可以好维护一点。
我们判断有没有解就是判断所有 \(B_i\) 是否有交。然而这很困难,因为 \(B_i\) 是若干个正方形的并。我们从实际意义上出发:如果一个人选择去地铁站,那么所有 \(D_i\) 小于他的人也会去地铁站。这些人可以那个人跟着走,显然距离不会超过 \(d\)。因此,将 \(B_i\) 分成两个部分:以出发点为中心的正方形 \(B_1\) 和以地铁站为中心的正方形的并 \(B_2\)。将所有点按 \(D_i\) 从大到小排序,我们枚举第一个选择去地铁站的人 \(i\),那么能选择的位置就是 \({B_1}_1\cap {B_1}_2\cap \cdots\cap {B_1}_{i-1}\cap {B_2}_{i}\)。
因为 \(B_1\) 是单个正方形,因此一段前缀的交是容易维护的,问题在于如何判断这段前缀交和多个正方形是否有交。考虑到这些正方形的边长都一样,因此只需要存在中心点在某个范围内,就和当前正方形有交,不难看出这个范围也是正方形。那么我们就是要判断某个二维范围内是否有点,可以用主席树做到 \(O(\log n)\)。只需要一个 \(i\) 有解,当前距离 \(d\) 就有解。
至于 \(D_i\) 的求解,可以随意用数据结构做到 \(O(n\log^k n)\),因此总复杂度是 \(O(n\log n\log V)\) 的。
CF1218B. Guarding warehouses
考虑一个更简单的版本:我们可以在 \(x\) 轴上平行于 \(y\) 轴监控,问能够监控到的面积。这个问题我们可以通过扫描线解决,因为离散化后,相邻的两个 \(x\) 坐标之间会有若干个不相交的线段,那么我们只需要计算出第一条线段和第二条线段之间的面积即可,可以通过计算两条线段到 \(x\) 轴之间的面积差解决。至于维护线段的顺序可以用 set
简单实现。
而这个问题只需要将对 \(x\) 坐标扫描线改为对极角扫描线即可。和上面同理,离散化后两条相邻的从原点发出的射线之间也有若干个不相交的线段,计算两条线段和原点组成的三角形的面积差即可算出这段对答案的贡献。线段排序依然用 set
实现,以当前极角与线段的交点到原点的距离为关键字排序,复杂度就是 \(O(n\log n)\) 的。
在实现的过程中要注意一些细节:
- 扫描线是有起始点的,因为极角形成了一个环,因此会有跨过起始点的情况。这时候要将线段断成两段,一段从距起始点 \(\epsilon\) 出发,一段到距起始点 \(\epsilon\) 结束。
- 考虑到一个极角开始的线段可能有若干条,在加入
set
时交点可能会相同,或因为掉精导致线段顺序插入反,需要将当前极角旋转 \(\epsilon\) 度。 - 因为删除的时候可能因为掉精而找不到要删除的元素,所以可以存下每一个元素插入时的迭代器,删除通过删除迭代器完成。