【算法竞赛 - 数据结构】Cube Stacking（并查集+树型前缀和）

Livinfly

发布于 2022-10-26 16:24:09

1990

发布于 2022-10-26 16:24:09

文章被收录于专栏：LivinflyLivinfly

题目跳转

[POJ1988]()

题目大意

有n堆正方体，有两个操作

M：把x所在堆移到y所在堆上方
C：输出x下面有多少个正方体

思路

并查集 - 树型前缀和

数组含义：

fa[] 并查集的父亲数组
siz[] 记录并查集大小
cnt[] 用作前缀和的数组

因为每次移动后，fx的父节点变为fy（fy在fx下面），cnt标记的对象fx不会重复。在路径压缩的同时累加好，所以在输出结果前要累加一次。

CODE

#pragma GCC optimize(2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <typeinfo>

using namespace std;

typedef long long LL;

const int N = 3e4 + 10;

int fa[N], siz[N], cnt[N];

int get_fa(int x)
{
  if (fa[x] == x)
    return x;
  int t = fa[x];
  fa[x] = get_fa(fa[x]);
  cnt[x] += cnt[t];
  return fa[x];
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  for (int i = 1; i < N; i++)
    fa[i] = i, siz[i] = 1;
  int T;
  cin >> T;
  while (T--)
  {
    char op[2];
    cin >> op;
    if (*op == 'M')
    {
      int x, y;
      cin >> x >> y;
      int fx = get_fa(x), fy = get_fa(y);
      if (fx != fy)
      {
        fa[fx] = fy;
        cnt[fx] = siz[fy]; // cnt加过的，都不会再成为祖宗
        siz[fy] += siz[fx];
      }
    }
    else
    {
      int a;
      cin >> a;
      get_fa(a);
      cout << cnt[a] << endl;
    }
  }
  return 0;
}
/*
  做类似树形前缀和的优化
*/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年08月13日，如有侵权请联系 cloudcommunity@tencent.com 删除

ode