一张\(n\)个点的图，初始没边，然后要求你支持以下操作：

• 给定\((x, y)\)，在\(x\)和\(y\)两点间添加一条长度为\(i\)的边（假设这是第\(i\)次操作）。
• 给定\(k\)，删除当前图中边权最大的\(k\)条边。
• 撤销上一次操作。保证存在上一次操作且不是撤销操作。

共\(m\)次操作，每次操作后输出当前图最小生成树的边权和（不存在的话输出\(0\)）。

\(1\leq n\leq 300000, 1\leq m\leq 500000\)。

一开始往可持久化XXX上想，脑袋炸了……虽然好像也能做？

假如说只有加边和删边操作，那怎么做呢？注意到后面的边一定不会有前面的边优，所以加进来的边如果能减小当前最小生成森林的联通块数，那就加上这条边。删除操作的话，注意到一条在最小生成森林中的边如果被删除了那么在前面不会有边来替代它的作用，所以删除的时候就需要撤销在并查集中的合并操作就行了，因此我们用栈来维护当前按时间顺序加进来的所有边对并查集的影响，删除的时候撤销就行。可撤销并查集也很好实现，写一个只用启发式合并不用路径压缩的并查集就行了。

不过撤销操作有一些毒瘤呢……其实也好做，如果说上一次是加边操作的话那么这一次撤销就等于删一条边了；如果上一次是删除操作的话，那么我们在上一次操作的时候就不要真的删除\(k\)条边。但是这样一来上一次操作又不好统计答案……其实也好弄，我们维护当前前\(i\)小的边形成的最小生成森林的边数和边权和就行了。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 500005;
using pii = std::pair<int, int>;
int n, m;
int p[maxn], s[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i; s[i] = 1;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return get_fa(p[x]);
  }
}
pii merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x == y) return {-1, -1};
  if(s[x] > s[y]) std::swap(x, y);
  p[x] = y; s[y] += s[x];
  return {x, y};
}
void undo(const pii &e) {
  int x = e.first, y = e.second;
  if(x > 0) p[x] = x, s[y] -= s[x];
}

using event = std::pair<int, pii>;
struct Query {
  char typ; int x, y;
  Query(char c = '\0', int a = 0, int b = 0) {
    typ = c; x = a; y = b;
  }
};
const int maxm = 500005;
using ll = long long;
Query Q[maxm]; ll sit[maxm]; int siz[maxm];
ll ans[maxn];
void solve() {
  int sz = 0;
  init_dsu();
  std::stack<event> S;
  for(int i = 1; i <= m; i ++) {
    if(Q[i].typ == 'A') {
      sz ++; sit[sz] = sit[sz - 1]; siz[sz] = siz[sz - 1];
      int x = Q[i].x, y = Q[i].y;
      pii delta = merge_set(x, y);
      if(delta.first > 0) {
        sit[sz] += (ll)i; siz[sz] ++;
      }
      S.push({i, delta});
      ans[i] = (siz[sz] == n - 1) ? sit[sz] : 0;
    } else if(Q[i].typ == 'D') {
      int k = Q[i].x;
      if(Q[i + 1].typ == 'R') {
        int tt = sz - k;
        ans[i] = (siz[tt] == n - 1) ? sit[tt] : 0;
      } else {
        sz -= k;
        while(k --) {
          auto p = S.top().second; S.pop();
          undo(p);
        }
        ans[i] = (siz[sz] == n - 1) ? sit[sz] : 0;
      }
    } else {
      if(Q[i - 1].typ == 'A') {
        sz --;
        auto p = S.top().second; S.pop();
        undo(p);
      }
      ans[i] = (siz[sz] == n - 1) ? sit[sz] : 0;
    }
  }
  for(int i = 1; i <= m; i ++) {
    printf("%lld\n", ans[i]);
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    char S[10]; scanf("%s", S);
    if(S[0] == 'A') {
      int x, y; scanf("%d%d", &x, &y);
      Q[i] = Query('A', x, y);
    } else if(S[0] == 'D') {
      int x; scanf("%d", &x);
      Q[i] = Query('D', x);
    } else {
      Q[i] = Query('R');
    }
  }
  solve();
  return 0;
}

• 相关文章
• 全局相关文章