Submission #59857183

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5e5+5;

int n, q;

int par[N], sz[N], col[N], mn[N], mx[N], ans[N];

int find(int u) {
  return par[u] = par[u] == u? u: find(par[u]);
}

void unite(int u, int v) {
  u = find(u);
  v = find(v);
  assert(col[u] == col[v]);
  if (u == v) return ;
  if (sz[u] < sz[v]) swap(u, v);
  par[v] = u;
  sz[u] += sz[v];
  mn[u] = min(mn[u], mn[v]);
  mx[u] = max(mx[u], mx[v]);
}

void assign(int u, int c) {
  int p = find(u);
  ans[col[p]] -= sz[p];
  col[p] = c;
  ans[col[p]] += sz[p];

  int v = mn[p] - 1;
  if (v >= 0 and col[find(v)] == col[find(u)]) {
    unite(find(v), find(u));
  }
  int w = mx[p] + 1;
  if (w < n and col[find(w)] == col[find(u)]) {
    unite(find(w), find(u));
  }
}

void solve () {
  cin >> n >> q;
  iota(par, par + n, 0);
  iota(col, col + n, 0);
  iota(mn, mn + n, 0);
  iota(mx, mx + n, 0);

  fill(sz, sz + n, 1);
  fill(ans, ans + n, 1);

  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      int i, c; cin >> i >> c; i--; c--;
      assign(i, c);
    }
    else {
      int c; cin >> c; c--;
      cout << ans[c] << "\n";
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int t = 1;
  // cin >> t;
  for (int i = 1; i <= t; ++i) {
    solve();
  }
  return 0;
}

Submission Info

Judge Result