阅读《记录一类分治方法》笔记
题一
\(n\) 个点的无向图,边有边权。\(q\) 次操作,每次操作是添加/删除一条边、修改一条边的边权、查询最小生成树这四种之一。
前言
其实只看了题一,后面都还没看呢。
看到这个感觉和 P7457 [CERC2018] The Bridge on the River Kawaii 很像,感觉很牛。想看看这个做法能不能推广到这题。
然后脑子有些混乱,觉得很能推广啊,想写一发代码。然后代码写完发现 P7457 是询问两点连通性。这和最小生成树不一样。很搞笑了。
所以只能再开一篇把写的东西搬过来了。
思路
原文对我来讲有些简略,这里会讲的更详细一点。
考虑我们有 \(O(m+q)\) 条边,每条边在一个时间区间内有权值 \(w_i\),在其他时刻权值为 \(inf\),求最小生成树。离线。
设边的全集是 \(E\),存在一些时刻权值是 \(inf\) 的边集是 \(Q\)。
把 \(Q\) 里所有边的权值设为 \(-inf\),跑一遍最小生成树,选上的 \(E\) 里面的边无论任何情况都是必选的。所有可以缩掉这些必选边。这样我们的点数变成了 \(O(|Q|)\)。
把 \(Q\) 里所有边的权值设为 \(inf\),跑一遍最小生成树,没有选上的 \(E\) 里面的边无论任何情况都不会被选择。所以可以删掉这些没用的边。这样我们的边数又变成 \(O(|Q|)\) 了。
对于当前分治区间,集合 \(E\) 定义为所有时间区间包含了整个分治区间的边。\(Q\) 定义为所有时间区间没有包含整个分治区间的边。
按照上面的方法,我们可以把点数和边数都变成 \(O(|Q|)\)。
\(Q\) 有多少条边?因为每次操作只会影响一条边,并确定这条边的时间区间的左/右端点。所以存在一个端点在当前分治区间内的边的数量,关于分治区间长度线性,即 \(O(len)\)。
既然我们保证了分治区间的点数和边数,那么每个分治区间把已经可以确定的点和边确定,有效的点和边留下即可。
总时间复杂度 \(O(q \log q)\)(并查集复杂度当常数看了)。