有编号为1~n
的n个盒子,最初每个盒子里都有1个球,颜色为c[i]。有Q次询问,每次给出{a[i],b[i]},将编号为a[i]的盒子里的球全放进编号为b[i]的盒子里,要求输出操作后b[i]中有多少种颜色的球?
1<=n,Q<=2e5; a[i]!=b[i]
用map维护每个盒子里不同颜色的球数,模拟即可,注意要用启发式合并。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
const ll inf = 1e18;
///////////////////////////////////////////////
const int N = 200005;
map<ll,ll> cnt[N];
int n, Q;
void solve() {
cin >> n >> Q;
rep(i,1,n) {
ll c;
cin >> c;
cnt[i][c] += 1;
}
rep(i,1,Q) {
ll a, b;
cin >> a >> b;
if (cnt[a].size() < cnt[b].size()) {
for (auto [k,v] : cnt[a]) {
cnt[b][k] += v;
}
cnt[a].clear();
} else {
for (auto [k,v] : cnt[b]) {
cnt[a][k] += v;
}
cnt[b].clear();
swap(cnt[a], cnt[b]);
}
cout << cnt[b].size() << "\n";
}
}
int initialize = []() {
cin.tie(0)->sync_with_stdio(0);
return 0;
}();
int main() {
int t = 1;
while (t--) solve();
return 0;
}
标签:cnt,盒子,int,abc329F,ll,cin,彩球,rep
From: https://www.cnblogs.com/chenfy27/p/18097747