251006 模拟赛
T3
给你两个图 \(G_1,G_2\)，点集相同，边集不同，边有边权。你可以选择两个整数权值 \(a,b\)，然后保留 \(G_1\) 中边权不超过 \(a\) 的边，和 \(G_2\) 中边权不超过 \(b\) 的边。称两个点是连通的，要么他们在第一个图中连通，要么在第二个图中连通。请你最小化 \(a+b\) 的值，使得相互连通的点对数量不小于给定的常数 \(k\)。
\(n,m_1,m_2\le 2\times 10^5,~k\le\frac{n(n+1)}{2}\)
首先，\(a,b\) 一个上升，另一个就下降，反之亦然，具有单调性。考虑双指针，对一个图维护加边，另一个图维护删边，动态维护连通点对数。发现点对数可以拆成在 \(G_1'\) 中连通，\(G_2'\) 中连通，同时在 \(G_1',G_2'\) 中连通三部分，分别记为 \(ans1,ans2,ans3\)，那么在 \(ans1+ans2-ans3\ge k\) 时更新答案即可。其中 \(ans1,ans2\) 是好做的。对于 \(ans3\)，考虑给 \(G_1'\) 和 \(G_2'\) 中的每个连通块赋一个随机权值，并定义一个点的权值等于其在两个图中两个连通块权值的异或。用哈希表维护所有异或值，容易在哈希表内维护 \(ans3\)。删边和加边操作直接启发式合并即可。时间复杂度 \(O(n\log n)\)。