专栏文章

不是 P6778 [Ynoi2009] rpdq 题解

NNelofus
P6778题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqqz5i9
此快照首次捕获于
2025/12/04 09:18
3 个月前
此快照最后确认于
2025/12/04 09:18
3 个月前
查看原文
どんな辛い世界の闇の中でさえ
きっとあなたは輝いて
这是一个搞笑做法，常数非常非常巨大，光排序就要排总长达 1.6×1081.6\times 10^8 以上的序列，实际上这个做法并不能通过。
晚上睡觉的时候冥想出来的神秘做法，不会 Top Cluster 树分块啊！
首先
∑l≤i<j≤rdis⁡(i,j)=∑l≤i<j≤rdep⁡(i)+dep⁡(j)−2dep⁡(LCA⁡(i,j))\sum_{l\le i<j\le r}\operatorname{dis}(i,j)=\sum_{l\le i<j\le r}\operatorname{dep}(i)+\operatorname{dep}(j)-2\operatorname{dep}(\operatorname{LCA}(i,j))
即
∑i=lr(r−l)dep⁡(i)−2∑l≤i<j≤rdep⁡(LCA⁡(i,j))\sum_{i=l}^{r}(r-l)\operatorname{dep}(i)-2\sum_{l\le i<j\le r}\operatorname{dep}(\operatorname{LCA}(i,j))
所以我们只要求出后面那个东西就行了。显然这个东西分治合并很倒闭，所以直接上莫队。那我们每次就是要求出
∑i=lrdep⁡(LCA⁡(i,z))\sum_{i=l}^{r}\operatorname{dep}(\operatorname{LCA}(i,z))
此事在 [LNOI2014] LCA 中亦有记载。直接套用那个做法就有 O(nmlog⁡n)\mathcal O(n\sqrt m\log n)，显然错干净了。
考虑莫队有 O(nm)\mathcal O(n\sqrt m) 次修改，O(m)\mathcal O(m) 次查询的事实。试图直接在原来的莫队上平衡掉这个东西显然非常困难，大概要一点树分块的东西，反正我不会啊！那么我们就只能先二次离线。
那么经典的，令贡献
f(z,[l,r])=∑i=lrdep⁡(LCA⁡(i,z))f(z,[l,r])=\sum_{i=l}^{r}\operatorname{dep}(\operatorname{LCA}(i,z))
现在就有三类贡献：
  1. f(i,[1,i])f(i,[1,i])
  2. f(i,[1,i−1])f(i,[1,i-1])
  3. ∑z=lrf(z,[1,i])\sum_{z=l}^{r}f(z,[1,i])
显然只有这个
∑z=lrf(z,[1,i])\sum_{z=l}^{r}f(z,[1,i])
做起来是困难的，我们来讨论这个东西怎么做。实际上我们就是要对点集 [1,i][1,i] 对点集 [l,r][l,r] 的贡献。
讨论一下点集 [l,r][l,r] 的性质：
  1. 只有 O(m)\mathcal O(m) 个。
  2. 总长是 O(nm)\mathcal O(n\sqrt m) 的。
既然总长有保证，那么我们总之先放一个虚树上去。
好像还是不太行，首先我们希望的是虚树的每一条边都是边长乘上某个贡献系数。
设 s1us1_u 表示 uu 子树中，编号为 [1,i][1,i] 的点的数量，s2us2_u 表示 uu 子树中，编号为 [l,r][l,r] 的点的数量。
考虑原树上，每个点的贡献都应该是 (dep⁡(u)−dep⁡(fa⁡(u)))⋅s1u⋅s2u(\operatorname{dep}(u)-\operatorname{dep}(\operatorname{fa}(u)))\cdot s1_{u}\cdot s2_{u}
我们把 [1,i][1,i] 的点和 [l,r][l,r] 的点去重后一起加入虚树，现在虚树上一条边上的所有原树的点都有 s1s_1 和 s2s_2 是相同的。在虚树上直接进行上述过程，也是正确的。
每次都要把 [1,i][1,i] 全部加进去，显然是 O(nm)\mathcal O(nm) 的。
不过这个问题不大，我们直接根号重构，一个显然的事实是，给定点集 SS，每次询问 zz，求
∑u∈Sdep⁡(LCA⁡(u,z))\sum_{u\in S} \operatorname{dep}(\operatorname{LCA}(u,z))
可以 O(n)\mathcal O(n) 预处理 O(1)\mathcal O(1) 询问，无非是预处理先做一次子树和，再做一次根链前缀和。
那么，维护一个小集合和一个大集合，每次移动 ii 的时候往小集合里加入一个点，每次询问时把小集合里的点和 [l,r][l,r] 一起拉出来跑虚树，然后对于 [l,r][l,r] 里的每个点，询问大集合对其的贡献。如果散点集合的大小 >n>\sqrt n，那就把小集合里的所有点移动到大集合里，然后对大集合重新做一次预处理。
显然小集合大小总是 O(n)\mathcal O(\sqrt n)，mm 次查询总共贡献为 O(mn)\mathcal O(m\sqrt n)，大集合做 O(n)\mathcal O(\sqrt n) 次预处理，每次预处理 O(n)\mathcal O(n)，所以复杂度为 O(nn)\mathcal O(n\sqrt n)。
上面预设了一个事情：能做到 O(n)\mathcal O(n) 排序，否则不能线性建虚树，需要写一个基数排序。可以底数 Base\mathrm{Base} 取 128128，排三轮。
总复杂度为 O(mn+nm+nn+Base⋅m)\mathcal O(m\sqrt n+n\sqrt m+n\sqrt n+\mathrm{Base}\cdot m)。
注意到本做法显然常数大得吓人，不可能通过。是谁在对拍带卡常狂写 16kb16\text{kb} 代码发现卡不进去之后才开始考虑做法的常数问题呢？

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...