CF *3000 数据结构题
A CF464E The Classic Problem
\(\text{Link}\)
- 题如其名,经典套路。
这种非传统最短路题我们可以考虑模拟 Dijkstra,实际上本题就是使用 Dijkstra,问题在于如何存储以及比较两个边权的大小。观察到边权是在二进制下存储的,且每一条边只有一位是 \(1\)。所以我们在二进制下修改边权时每次不会修改太多,具体的,找到 \(x_i\) 右侧第一个 \(0\),将这个 \(0\) 改为 \(1\),然后将这一段的 \(1\) 全部改成 \(0\) 即可。
那么操作实际上就是单点赋值,区间覆盖,线段树可以直接维护。而同时我们还需要保留原有的信息,所以考虑利用主席树存储边权信息。最后考虑怎样判断大小,这也是经典问题,在主席树上维护区间哈希值,二分找到第一个不同的位比较大小即可。
上述操作显然可以在 \(O(\log n)\) 的时间内完成,加上 Dijkstra 的复杂度,总复杂度 \(O(n\log^2 n)\)。
B CF526F Pudding Monsters
\(\text{Link}\)
- 经典套路。
我们记录每一行上的怪物出现在第几列,设为 \(a_i\)。那么一个区间合法的条件就是 \(\max -\min =r-l\),移项后就是 \((\max -\min)-(r-l)=0\),显然左边式子最小值就是 \(0\),维护最小值个数即可。复杂度 \(O(n\log n)\)。
C CF603E Pastoral Oddities
\(\text{Link}\)
- 之前在线段树分治的题单里,比较经典的题目。
先考虑什么样的图是合法的,可以发现:当且仅当所有联通块大小为偶数的时候才有解。那么我们可以得到一个整体的做法:先对所有边从小到大排序,然后不断加入边直到满足条件,最后一个加入的边就是答案。
回到原题,发现我们每一条边在答案中存在的时间构成了一个区间,于是考虑线段树分治。我们从右向左求解答案,递归到一个子节点时,如果当前的答案不合法,那么不断加入边权更大的边,此时我们就知道这些边的存活时间终点是当前点,将这些边加入线段树。否则的话不作处理。
判断的部分用可撤销并查集维护即可,复杂度 \(O(n\log^2 n)\)。
D CF1446D2 Frequency Problem (Hard Version)
\(\text{Link}\)
- 神秘结论题,好像是很常见的套路。
首先有一个结论:答案区间中的一个众数必定是全局众数。证明考虑反证,如果答案区间的两个众数 \(a,b\) 没有全局众数 \(c\),考虑扩展区间。此时我们有 \(cnt_a>cnt_c\),而当我们扩展到全局时会有 \(cnt_a\le cnt_c\),由于变化是连续的,所以中间一定存在一个时刻满足 \(cnt_a=cnt_c\),此时取这个区间是更优的。
然后考虑枚举另一个众数,暴力做的话可以利用前缀和做到 \(O(nV)\),可以通过简单版。不过我们知道在序列中有一个关系是出现次数为 \(i\) 的数的个数乘上 \(i\) 小于等于 \(n\),那么我们可以考虑根号分治。
- 对于 \(cnt_i\ge \sqrt n\) 的数,这种数最多有 \(\sqrt n\) 个,直接套用上面的暴力,复杂度 \(O(n\sqrt n)\)。
- 对于 \(cnt_i< \sqrt n\) 的数,我们枚举出现次数,然后利用双指针和桶求出区间众数出现次数为 \(i\) 的最长区间即可。复杂度 \(O(n\sqrt n)\)。
综上,总复杂度 \(O(n\sqrt n)\)。
E CF150E Freezing with Style
\(\text{Link}\)
- 写假了调了一个小时。
考虑我们要求的是中位数,经典套路是二分答案然后转化为 \(\pm 1\) 序列,判断是否有一个路径和 \(\ge 0\)。
树上路径问题自然考虑点分治,我们考虑怎样合并两个子树。我们枚举一个子树中的深度 \(x\),那么另一边的深度必须在 \([L-x,R-x]\) 之间,很显然这个区间的长度固定,可以单调队列求解出最大值,然后相加判断是否 \(\ge 0\) 即可。
不过对于点分治暴力合并的复杂度是 \(O(n^2)\) 的,一种解决办法是先按子树大小排序再处理。不过这样太麻烦,考虑到我们可以简单实现的是两个子树的合并,所以不妨考虑边分治,这样每次只用合并两个子树。复杂度 \(O(n\log^2 n)\)。
F CF997E Good Subsegments
\(\text{Link}\)
- B 题加强版。
和 B 题思路一致,依然维护最小值,但是现在我们要求的是区间中有多少子区间满足条件。离线扫描线,在每个右端点处给左侧的最小值的地方加一,然后查询区间和即可。复杂度 \(O(n\log n)\)。
G CF319E Ping-Pong
\(\text{Link}\)
- 有难度的线段树优化建图题目。
首先考虑连边,发现我们可以分为三类:
- 区间无交,不连边。
- 区间包含,被包含区间向包含区间连单向边。
- 区间相交,连双向边。
而我们要求判断的是能否从 \(a\) 走到 \(b\)。乍一看这十分不可做,因为这是有向图动态可达性。不妨先考虑简单情况,即没有单向连边的情况。此时我们可以将所有相交的区间直接用并查集连起来,然后只需要判断 \(a,b\) 在不在一个连通块即可。可以发现,每一个连通块都会覆盖满一个区间,记为 \([L,R]\)。
对于原题的情况,我们依然如此,但是不同的地方在于我们连通块对应的区间可能会有包含。我们知道我们可以从被包含的区间走向包含的区间,所以可以得到 \(a\) 可达 \(b\) 的充要条件:\(a\) 所在连通块的区间被 \(b\) 所在连通块的区间完全包含。
那么我们在线段树上维护一下所有区间,每次找出 \(l,r\) 和哪些区间有交,合并起来即可。由于保证后面的区间长度比前面大,所以后面的区间不会被前面的包含,因此直接找就是正确的,复杂度 \(O(n\log n)\)。
H CF696E ...Wait for it...
\(\text{Link}\)
- 树剖模板题,要把题先读懂。
删除权值前 \(k\) 小的点并输出好像不是很好做,不过我们可以转化一下。我们做 \(k\) 次求最小值操作,求出来时候再删掉即可。每个点做多删掉一次,所以复杂度是对的。
但是每个点上会有很多人,用 set
维护该点上的人,删除后从 set
中再取一个即可。复杂度 \(O(n\log^2 n)\)。
I CF1163F Indecisive Taxi Fee
\(\text{Link}\)
- 线段树在图论上的应用,需要对最短路的理解。
首先先随意找出一条 \(1\to n\) 的最短路,然后我们分类讨论一下这条边在不在这条最短路上。我们此时的最短路有两种可能,经过或不经过这条边。
-
如果不在最短路上。此时不经过这条边的最短路就是已经求出来的那一条。否则我们从 \(1,n\) 分别跑一边最短路求出到所有点的距离,然后经过这条边的最短路就是 \(\min(dis_{1,u}+w+dis_{n,v},dis_{1,v}+w+dis_{n,u})\)。
-
如果在最短路上。此时经过这条边的最短路还是刚刚的式子。而最困难的是不经过这条边的最短路怎么求。我们考虑从经过的其他边下手,假如我们的路径形如 \(1\to u\to v\to n\),很显然在这里面我们会经过一些最短路上的边。
记 \(l_u\) 表示从 \(1\to u\) 的最短路上至少要经过几条原最短路上的边, \(r_v\) 同理。那么上面的这条最短路没有经过 \([l_u+1,r_v]\) 上的任何一条边,我们可以将它的答案更新到这个区间上。那么我们维护一下区间取 \(\min\)、单点查询即可。复杂度 \(O(n\log n)\)。
J CF436F Banners
\(\text{Link}\)
- KTT 模板题。
首先我们枚举 \(c\),那么此时 \(b_i\ge c\) 的贡献我们就已知了。现在我们要确定一个 \(p\),使得 \(p\times \sum[b_i<c \land a_i\ge p]\) 的值最大。这个式子显然是一个 \(kx\) 的形式,并且在我们扫描线的时候我们会给一段前缀的 \(p\) 的 \(x\) 加一。
那么这个就可以用 KTT 维护了,复杂度 \(O(n\log^2 n)\) 直接过。
K CF793F Julia the snail
\(\text{Link}\)
- 吉司机线段树的应用。
考虑将把他放平变成一个序列,那么在序列上的这种问题我们可以考虑离线扫描线。枚举上界 \(r\),维护每个左端点能走到的最远点。
接下来考虑怎样更新,假如我们当前走到 \(r\),其对应左端点为 \(l\),考虑答案会怎样变化。很显然,此时所有起点位于 \([1,l]\),并且能够走到的最远点 \(\ge l\) 的点都可以往回走然后跳到 \(r\)。所以我们的操作是将一段区间 \(\ge l\) 的所有数改为 \(r\)。
这个操作看上去不好做,但实际上它和 chkmin
是本质相同的。用吉司机线段树维护一下即可,复杂度 \(O(n\log n)\)。
L CF1178G The Awesomest Vertex
\(\text{Link}\)
- 经典拆绝对值算贡献。
容易发现后面的 \(|\sum b|\) 是不变的,所以我们只需要考虑前面的部分。那么我们维护的实际上就是一个 \(kx\) 的状物,拍到 DFS 序上就是区间加区间查。但是现在的问题是我们的 \(x\) 是带绝对值的,不好维护,考虑经典套路,我们知道:
所以我们对每个节点维护两个值 \(kx\) 和 \(-kx\),每次给 \(x\) 加上一个正值,最后求最大值。KTT 即可,复杂度 \(O(n\log^2 n)\)。
M CF773E Blog Post Rating
\(\text{Link}\)
- 手玩找出操作的本质即可用数据结构维护。
容易发现我们一定将 \(a_i\) 排成升序最优,并且我们的 \(f\) 值会先一直递减,随后递增。先找到这个转折点,然后考虑 \(f\) 值随后如何变化。容易发现在经过第 \(i\) 个博客之后的 \(f\) 值 \(f_i\) 有递推式 \(f_i=\min(f_{i-1}+1,a_i)\)。根据经典套路我们知道这等于 \(\min a_i+n-i\)。
那么我们现在要找出转折点,也就是找出第一个 \(-i\le a_i\) 的位置,转化一下就是 \(a_i+i\ge 0\)。用线段树维护当前所有的 \(a_i\),用线段树二分即可。\(a_i+n-i\) 的最小值显然也可以直接维护。复杂度 \(O(n\log n)\)。
N CF331D3 Escaping on Beaveractor
\(\text{Link}\)
- 倍增维护走路,但是代码细节很多。
容易发现我们的操作次数很多,肯定无法枚举。考虑这是一个走路题,我们用倍增来维护。记 \(f_{i,j}\) 表示从第 \(i\) 个点出发走 \(2^j\) 条线段到达哪一条线段,\(g_{i,j}\) 表示从第 \(i\) 个点出发走 \(2^j\) 条线段到达终点后需要多长时间。现在需要考虑 \(f_{i,0},g_{i,0}\) 怎么求,我们从四个方向上各做一次扫描线,用线段树维护当前位置上的线段编号即可。
求答案的时候用倍增数组走即可,最后不够的要强制退回来。复杂度 \(O(n\log n)\),代码比较困难。
O CF185E Soap Time! - 2
\(\text{Link}\)
先考虑二分答案。考虑到每个人会有一个离他最近的车站,把这个距离记作 \(d_i\)。那么很显然,走到车站的一定是一个按 \(d_i\) 排序后的前缀,这样不会更劣。我们枚举这些人,那么剩下的人自然不能走到车站,我们先对他们能走到的范围求交,记作 \(A\)。
然后走到车站的这些人需要走到这个交 \(A\) 里面,此时每个车站能往外走的距离是 \(mid-\max d\),不过枚举每个车站判断与 \(A\) 是否有交复杂度不能接受,考虑让这个过程反过来,我们看哪个范围里的车站能够走到 \(A\) 里面。不难发现这就是将 \(A\) 向外扩大 \(mid-\max d\) 后的区域。我们查询这个区域里是否有车站即可。
不过此时的区域难以表示,原因在于在曼哈顿坐标系下我们的区域是一个菱形。考虑转化成切比雪夫坐标系,这样上述所有区域都是矩形,用主席树即可查询。复杂度 \(O(n\log^2 n)\)。
最后一个问题是 \(d_i\) 怎么求,我们依然二分答案,然后看这个范围内是否有车站即可。复杂度还是两只老哥的。
P CF1218B Guarding warehouses
\(\text{Link}\)
- 神秘计算几何。
先考虑在普通坐标系上的问题,我们求光线从 \(x\) 轴射出的答案。我们在 \(x\) 轴上从左往右扫描线,每一次我们求出当前区间内最下面的两条线段,用两个梯形面积做差即可。
然后考虑放到极坐标系上,我们在极角上扫描线,用 set
维护当前离原点最近的两条线段,求两个三角形的面积差即可。复杂度 \(O(n\log n)\),常数比较大,并且精度要控制好。