LOJ #3540. 「JOI Open 2018」山体滑坡

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\,]\)。我们现在要实现的操作就是:

  1. 加边;删边
  2. 询问当前最小生成树的森林中有多少条边的权值 \(\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

上一篇:在家运维不用慌 | 盘点那些远程运维中的云上利器


下一篇:python list_2