「2019-08-08 省常中互测」合并果子

Description

首先给你$n$个柠檬,每个各成一堆,每次给出以下两种操作:

  • 1 a b,将$a$和$b$所在柠檬堆合并成一堆。
  • 2 a b,将$a$所在柠檬堆内所有的柠檬都挤出$b$的柠檬水。

最后统计每一个柠檬被挤出多少柠檬水。

Data Range

$n\leq 1000000$

Solution

考虑维护并查集。

然后每一次操作我们都新建一个虚拟节点,作为两个合并的并查集的顶部的父亲。

对于每一次挤出操作,我们都把标记加在并查集的$top$,这样可以保证不会互相干扰,表示这个子树内的所有节点都多挤出了$val$的柠檬水。

然后把这个标记类似于树上差分的做法,分别统计到各个节点上即可。

千万不要像我一样,把前缀和打成后缀和。。。

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define REP(i, s, t) for (int i = (s), i##ed = (t); i <= i##ed; i ++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T> void chkmin(T &x, T y) {
  x = x < y ? x : y;
}
template <typename T> void read(T &x) {
  x = 0; bool w = 0; char ch = 0;
  for (; !isdigit(ch); ch = getchar()) w |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  x *= w ? -1 : 1;
}
template <typename T> void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T> void write(T x, char ch) {
  write(x);
  putchar(ch);
}
template <typename T> void writeln(T x) {
  write(x);
  puts("");
}
const int N = 1000000 + 5;
int n, q, node_cnt;
int fa[N], val[N];
vector<int> g[N];
bool vis[N];
int gf(int x) {
  return x == fa[x] ? fa[x] : fa[x] = gf(fa[x]);
}
void dfs(int u) {
  vis[u] = 1; 
  for (int i = 0; i < (int) g[u].size(); i ++) {
    int v = g[u][i]; 
    if (vis[v]) continue; 
    val[v] += val[u];
    dfs(v); 
  }
}
int main() {
//  freopen("merge.in", "r", stdin);
//  freopen("merge.out", "w", stdout);
  memset(val, 0, sizeof(val)); 
  memset(vis, 0, sizeof(vis)); 
  read(n); read(q);
  node_cnt = n;
  for (int i = 1; i <= n; i ++) fa[i] = i;
  while (q --) {
    int opt, x, y; 
    read(opt); read(x); read(y); 
    if (opt == 1) {
      int p = gf(x), q = gf(y);
      if (p == q) continue;
      node_cnt ++; 
      fa[p] = fa[q] = node_cnt;
      val[node_cnt] = 0; 
      fa[node_cnt] = node_cnt; 
      g[node_cnt].push_back(q);
      g[q].push_back(node_cnt);
      g[node_cnt].push_back(p);
      g[p].push_back(node_cnt);
    }
    else {
      int p = gf(x); 
//      cout << "add : " << p << ' ' << x << endl;
      val[p] += y; 
    }
  }
//  for (int i = 1; i <= n * 2; i ++) {
//    cout << val[i] << ' '; 
//  }
//  cout << endl;
  for (int i = 1; i <= n; i ++) {
    int top = gf(i);
    if (!vis[top]) { 
      dfs(top);
    }
  }
  for (int i = 1; i <= n; i ++) {
    write(val[i], " \n"[i == n]);
  }
  return 0; 
}
最后修改:2019 年 08 月 24 日 08 : 54 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论