数据结构题单

· · 题解

1. LuoguP2048 [NOI2010]超级钢琴

【题意】

给定一条长为 N 序列 A[i] ，求出 长度 在 [L,R] 内的前 K 大的区间和之和。

N,K\leq 5\times 10^5

【题解】

一道好题

做法：堆 套 ST表

要表示表示所有的区间，有两个自由度(左右端点)和一个限制(区间长度)。我们不能枚举所有的区间，考虑维护可能的候选集合。

枚举左端点 l，使得区间和最大的右端点就是

r={\rm argmax}\begin{Bmatrix}\sum\limits_{i=0}^{len-1} A[l+i]\mid len\in[L,R]\end{Bmatrix}

求出前缀和 rsum[i]，得到

r=&{\rm argmax}\begin{Bmatrix}rsum[l+len-1]-rsum[l-1]\mid len\in[L,R]\end{Bmatrix}\\ =&{\rm argmax}\begin{Bmatrix}rsum[l+len-1]\mid len\in[L,R]\end{Bmatrix}-rsum[l-1] \end{aligned}

转化为区间最值问题。可以用线段树或ST表解决。

所有的 l 都能找到固定的 最优解 r，再从所有的 [l,r] 中选取最优解就是区间和最大的区间。相当于最值套最值。

用一个堆来维护这些值。堆里面一开始存储了所有共 N 个 l。由于每个 l 可以通过区间最值求出 r ，所以每个 l 又相当于维护了 [l+L-1,l+R-1] 内的 r 中的最优解。

构造将区间 [l,r] 从堆中删除的方法。我们发现只需要将 l 的维护区间去除掉 r 即可。

所以我们在堆中储存一个三元组 (lb,rb_1,rb_2) ，[rb_1,rb_2] 就是 lb 的维护区间。去除点r相当于将区间分成两部分。每次将 (lb,rb_1,rb_2) 弹出，再弹入 (lb,rb_1,r-1),(lb,r+1,rb_2) 就可以做到了。

最后，用线段树维护每个 l 对应的区间的计算时间复杂度为 O(\log N) ，这导致堆中的比较函数是 O(\log N)的，总复杂度为 O(N+K\log^2N)。

所以我们用 O(1) 查询的ST表来平衡复杂度。

最终时间复杂度为 O(N\log N+K\log N)，空间复杂度 O(N\log N)。

LuoguP4211 [LNOI2014] LCA

【题意】

给定一棵N个点的树，询问Q次，每次给定(l,r,z)，求\sum_{k=l}^rdep[LCA(k,z)]

N,Q\leq 5\times10^4

【题解】

一开始想了好久的树剖套主席树。。。

发现树剖是要修改线段树的多处信息的。。。

所以不能用主席树，复杂度会爆炸。。。

或者是因为我菜？

正解：树剖,离线做法

言归正传，题目要求这个

\sum_{k=l}^rdep[LCA(k,z)]

下面乱搞一通。第一条

\sum_{k=l}^rdep[LCA(k,z)]=\sum_{k=1}^rdep[LCA(k,z)]-\sum_{k=1}^{l-1}dep[LCA(k,z)]

这不是废话么

第二条

两个点LCA的深度其实就是两个点到根的公共路径的长度

定义点 k 到根的路径上的点集为 path(k)，那么

dep[LCA(k,z)]=\sum_{i\in \mathbb V}[i\in path(k)]\cdot[ i\in path(z)]

这不也是是废话么

更改一下枚举顺序，即得

\sum_{k=1}^n dep[LCA(k,z)] &=\sum_{k=1}^n\sum_{i\in \mathbb V}[i\in path(k)]\cdot[ i\in path(z)]\\ &=\sum_{i\in path(z)}\sum_{k=1}^n[i\in path(k)] \end{aligned}

观察一下，这条式子还是很好维护的

\sum_{k=1}^n[i\in path(k)]

就是每次给 path(k) 上的所有点点权+1之后点 i 的点权。

\sum_{i\in path(z)}

就是裸的树上路径求和

瞄一眼，题目没有要求强制在线。下次出题人反手就加上了

我们现在比较好处理的是\sum_{k=1}^n dep[LCA(k,z)]

于是我们把题目要求的询问 (l,r,z) 拆开成 (1,l-1,z)和(1,r,z)

将询问按右端点排序，用树上区间操作数据结构一个个地加上去。这样就不用每次重建线段树了。

最终复杂度是O(N\log^2N+Q\log^2N)

LuoguP2486 [SDOI2011] 染色

【题意】

给定一棵 N 个点的树，操作 M 次，每次将路径 (u,v) 染成颜色 c 或查询其颜色分段数。

N,M\leq 10^5,c\leq 10^9

【题解】

考虑链上的情况。尝试用线段树维护这两种操作。

先考虑如何查询。考虑如何去重。线段树属于典型的分治结构，考虑给出了子区间的颜色分段数，计算整个区间的颜色分段数。容易发现，只要区间相接的地方颜色相同，合并时答案减一即可。记录区间的左右端点颜色，发现也非常容易维护。

修改时打懒标记即可。再加上树剖，轻松转化为树上的情况。

P5838 [USACO19DEC] Milk Visits G from BenQ

表述相似的题。也可以考虑树剖，但是有更快的做法。

Luogu P4768 [NOI2018] 归程

Luogu P6773 [NOI2020] 命运

Luogu P3642 [APIO2016] 烟火表演

Luogu P4899 [IOI2018 D1T3] 狼人

CF757G Can Bash Save the Day?

下面的没有经验拿就不做了

bzoj4548

bzoj2957 楼房重建

bzoj4756

uoj515

cjoj 小\omega的仙人掌

牛客挑战赛30 某题

牛客挑战赛25 e