题意
\(n\)个人,每个人属于一个班级\(ci\),这些人会有些小团体(并查集)
两种操作:
分析
看\(1\)操作是并查集,每一个人一开始有一个权值,如果两个集体合并,那么需要将他们的权值合并
看上去就像是线段树合并(前段时间刚学的)
一开始所有人都有一个根,对于他们的班级权值为\(1\)
对于\(1\)操作,找到\(a\)和\(b\)的祖先节点,合并两者的线段树,并进行并查集合并
对于\(2\)操作,查询即可
数组要开大点,反正有\(1024MB\)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
//#define int ll
//#define ls st<<1
//#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e7 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int T = 1;
int ls[maxn], rs[maxn], val[maxn], n, tot;
int pre[maxn];
int find(int x) {
if (pre[x] != x)
pre[x] = find(pre[x]);
return pre[x];
}
int rt[maxn];
void Modify(int &u, int l, int r, int p) {
if (!u) u = ++tot;
if (l == r) {
val[u]++;
return;
}
int mid = l + r >> 1;
if (p <= mid) Modify(ls[u], l, mid, p);
else Modify(rs[u], mid + 1, r, p);
}
int merge(int u, int v, int l, int r) {
if (!u || !v) return u | v;
if (l == r) {
val[u] += val[v];
return u;
}
int mid = (l + r) >> 1;
ls[u] = merge(ls[u], ls[v], l, mid);
rs[u] = merge(rs[u], rs[v], mid + 1, r);
return u;
}
int query(int u, int l, int r, int p) {
if (l == r)
return val[u];
int mid = l + r >> 1;
if (p <= mid) return query(ls[u], l, mid, p);
else return query(rs[u], mid + 1, r, p);
}
void solve() {
int q;
cin >> n >> q;
rep(i, 1, n)rt[i] = i, pre[i] = i;
tot = n;
rep(i, 1, n) {
int c;
cin >> c;
Modify(rt[i], 1, n, c);
}
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
x = find(x);
y = find(y);
if (x == y)
continue;
merge(rt[x], rt[y], 1, n);
pre[y] = x;
} else {
x = find(x);
cout << query(rt[x], 1, n, y) << '\n';
}
}
}
signed main() {
start;
while (T--)
solve();
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章