P5385 [Cnoi2019] 须臾幻境

发布时间 2023-10-05 22:26:51作者: 音街ウナ

(无需 LCT 简化版:P4764)主要是记录一个 Trick 而非 LCT、主席树 等的使用。

给定无向图,\(q\) 次询问,求边权在 \([l,r]\) 内的边的生成子图的连通块数目。强制在线。

对于连通块问题,考虑提取生成森林。连通块数目等于顶点数减去 边数最多的生成森林的边数。

强制在线也可以先用离线思想预处理。于是我们显然 扫描线,相当于求加入边 \([1,r]\) 后,最少从某个最多生成森林 删去多少条边 使得不存在 \([1,l)\) 中的边。

显然这个最多生成森林应该(在边数最多基础上)所有边权都尽可能大,也就是 最大生成森林

因此若能直接预处理每个 \(r\) 对应的最大生成森林的边集,询问时直接查询其中权值位于 \([1,l)\) 中的边数即可。然而时空均不允许这样预处理。

首先对于最大生成森林,因为每次加入一条边 \((u,v)\) 最多断开原来路径 \(u\leftrightsquigarrow v\) 上的最小边。直接 LCT 维护即可。

但是仍然无法存下来。考虑第 \(i\) 条边随着 \(r\) 的增加出现又消失,会对 \(l\in[i,n], r\in[r_1,r_2]\) 的询问造成 \(-1\) 的贡献。于是询问就是一个在线二维数点,主席树即可。