LOJ #3540. 「JOI Open 2018」山体滑坡
设有无向图 \(G\)，对于 \(G\) 的每一个极大连通块 \(T\) 求出其任意生成树 \(T'\)，那么图 \(G\) 的极大连通块的个数就是 \(n-\sum|E_{T'}|\)，其中 \(E_G\) 为图 \(G\) 的边集。因此，我们只需要求出 \(\sum|E_{T'}|\) 即可。
注意到在询问 \((W,P)\) 之后的图 \(G'\) 不存在边 \((u,v)\) 满足 \(u\le P\) 且 \(P<v\)。于是我们可以拆成两部分统计：第一次统计点 \(0\sim P\) 组成的极大连通块，第二次统计点 \(P+1\sim n-1\) 组成的极大连通块。由于两次统计本质上一样，不妨思考如何实现第一次统计。
将每一条边 \(e(u,v)\) 的权值设为 \(w_e=\max\{u,v\}\)。对于一个确定的 \(P\)，容易发现图 \(G'\) 中不存在任何权值 \(w_e>P\) 的边 \(e\)。考虑 \(P\) 在逐渐增大的过程，图 \(G'\) 中的边逐渐变多，而其极大连通块个数逐渐减少。因此我们需要知道每一个极大连通块什么时候存在的。对于一个极大连通块 \(T\)，设其最小生成树为 \(T'_{\min}\)，那么当 \(P\ge \max\{E_{T'_{\min}}\}\) 时，该极大连通块存在。于是我们可以考虑当前图 \(G\) 的最小生成树森林。
设当前加入的边集为 \(E\)，图 \(G\) 的最小生成树森林为 \(G_{\min}\)。我们发现，对于 \(E\) 中的一条边 \(e\)，若 \(e\notin {G_\min}\)，那么 \(e\) 是没有贡献的；而若 \(e\in G_\min\)，那么当 \(P\ge w_e\) 时，就会对 \(\sum{|E_{G_\min}|}\) 产生 \(1\) 的贡献。因此对于一个确定的 \(P\)，此时边集 \(E\) 对答案的贡献就是 \(\sum\limits_{e\in G_\min}[\,w_e\le P\,]\)。我们现在要实现的操作就是：
- 加边；删边
- 询问当前最小生成树的森林中有多少条边的权值 \(\le P\)。
我们可以想到使用 \(\text{LCT}\) 维护最小生成树森林。但很麻烦的一点是，\(\text{LCT}\) 维护最小生成树不支持删除任意一条边。于是我们可以使用线段树分治将删边的操作变为回滚操作，然后就可以大力 \(\text{LCT}\) 维护了。总时间复杂度为 \(\mathcal O(n\log ^2n)\)，其中一个 \(\log\) 是线段树分治，另一个 \(\log\) 是 \(\text{LCT}\)。
参考代码
#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
static constexpr int Maxn = 2e5 + 5;
int n, m, q, cn;
vector<int> ans;
int val[Maxn];
inline bool val_cmp(int x, int y) { return val[x] > val[y]; }
namespace lct {
static constexpr int MaxN = 2e5 + 5;
bool rev[MaxN];
int fa[MaxN], ch[MaxN][2];
int tr[MaxN];
#define nroot(x) ((ch[fa[x]][0] == x) || (ch[fa[x]][1] == x))
#define getdir(x) (ch[fa[x]][1] == x)
inline void pushrev(int p) { swap(ch[p][0], ch[p][1]), rev[p] ^= 1; }
void pushdown(int p) {
if (rev[p]) {
if (ch[p][0]) pushrev(ch[p][0]);
if (ch[p][1]) pushrev(ch[p][1]);
rev[p] = false;
}
} // lct::pushdown
void pushup(int p) {
tr[p] = p;
if (ch[p][0]) tr[p] = min(tr[p], tr[ch[p][0]], val_cmp);
if (ch[p][1]) tr[p] = min(tr[p], tr[ch[p][1]], val_cmp);
} // lct::pushup
void rotate(int p) {
int par = fa[p], grd = fa[par];
bool dir = getdir(p);
ch[par][dir] = ch[p][dir ^ 1];
fa[ch[p][dir ^ 1]] = par; fa[p] = grd;
if (nroot(par)) ch[grd][getdir(par)] = p;
fa[par] = p, ch[p][dir ^ 1] = par;
pushup(par), pushup(p);
} // lct::rotate
void splay(int p) {
static int stk[MaxN], top; stk[top = 1] = p;
for (int t = p; nroot(t); ) stk[++top] = t = fa[t];
while (top) pushdown(stk[top--]);
for (int par = fa[p]; nroot(p); rotate(p), par = fa[p])
if (nroot(par)) rotate(getdir(p) == getdir(par) ? par : p);
} // lct::splay
void access(int p) {
for (int x = 0; p; x = p, p = fa[p])
splay(p), ch[p][1] = x, pushup(p);
} // lct::access
void make_root(int p) {
access(p), splay(p);
pushrev(p);
} // lct::make_root
int find_root(int p) {
access(p), splay(p);
while (ch[p][0]) pushdown(p), p = ch[p][0];
splay(p);
return p;
} // lct::find_root
void link(int x, int y) {
make_root(x);
fa[x] = y;
} // lct::link
void cut(int x, int y) {
make_root(x);
access(y), splay(y);
assert(fa[x] == y && ch[y][0] == x);
fa[x] = ch[y][0] = 0;
pushup(y);
} // lct::cut
} // namespace lct
namespace fen {
static constexpr int MaxN = 2e5 + 5;
int bit[Maxn];
void upd(int x, int v) {
for (; x <= n; x += x & -x) bit[x] += v;
} // fen::upd
int ask(int x) {
int r = 0;
for (; x; x -= x & -x) r += bit[x];
return r;
} // fen::ask
} // namespace fen
vector<pair<int, int>> qs[Maxn];
pair<int, int> e[Maxn];
vector<int> es[Maxn * 4];
void link_to(int p, int l, int r, int L, int R, int x) {
if (L >= r || l >= R) return ;
if (L <= l && r <= R) return es[p].push_back(x);
int mid = (l + r) / 2;
link_to(p * 2 + 0, l, mid, L, R, x);
link_to(p * 2 + 1, mid, r, L, R, x);
} // link_to
int stk[Maxn], top;
bool added[Maxn];
void del_edge(int i, bool Stack) {
int x = e[i].first, y = e[i].second;
lct::cut(i, x), lct::cut(i, y);
if (Stack) stk[++top] = i, added[top] = false;
fen::upd(val[i], -1);
} // del_edge
void add_edge(int i, bool Stack) {
int x = e[i].first, y = e[i].second;
lct::make_root(x);
if (Stack && lct::find_root(y) == x) {
if (val[lct::tr[x]] > val[i])
del_edge(lct::tr[x], true);
else return;
}
lct::link(i, x), lct::link(i, y);
if (Stack) stk[++top] = i, added[top] = true;
fen::upd(val[i], 1);
} // add_edge
void divide(int p, int l, int r) {
int rec_top = top;
for (const int &i: es[p]) add_edge(i, true);
if (l + 1 == r) {
for (const auto &[x, i]: qs[l])
ans[i] += fen::ask(x);
} else {
int mid = (l + r) / 2;
divide(p * 2 + 0, l, mid);
divide(p * 2 + 1, mid, r);
}
for (; top > rec_top; --top) {
if (added[top] == true)
del_edge(stk[top], false);
else add_edge(stk[top], false);
}
} // divide
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
n = N, m = (int)T.size(), q = (int)W.size();
ans.assign(q, 0);
for (int &x: X) ++x;
for (int &x: Y) ++x;
for (int &x: P) ++x;
for (int i = 0; i < m; ++i)
if (X[i] > Y[i]) swap(X[i], Y[i]);
map<pair<int, int>, int> ep;
cn = n;
for (int i = 0; i < m; ++i) {
if (T[i] == 0) {
ep[{X[i], Y[i]}] = i;
} else {
int &t = ep[{X[i], Y[i]}];
e[++cn] = {X[i], Y[i]};
link_to(1, 0, m, t, i, cn);
t = -1;
}
}
for (auto &[E, t]: ep)
if (t != -1) {
e[++cn] = E;
link_to(1, 0, m, t, m, cn);
t = -1;
}
for (int i = 0; i < q; ++i)
qs[W[i]].push_back({P[i], i});
for (int i = 1; i <= cn; ++i) lct::tr[i] = i;
#define calculate { \
for (int i = n + 1; i <= cn; ++i) val[i] = e[i].second; \
top = 0, divide(1, 0, m); \
}
calculate
for (int i = n + 1; i <= cn; ++i) {
e[i].first = n - e[i].first + 1;
e[i].second = n - e[i].second + 1;
swap(e[i].first, e[i].second);
}
for (int t = 0; t < m; ++t)
for (auto &[x, id]: qs[t]) x = n - x;
calculate
for (int &x: ans) x = n - x;
return ans;
} // simulateCollapse