作者：YooHoo | 来源：互联网 | 2023-06-05 17:50
时间限制: 1Sec 内存限制: 128MB提交: 33 解决: 11[提交][状态][讨论版][命题人:admin]题目描述Dove和Cicada是好朋友，他们经常在一起打扑
时间限制: 1 Sec 内存限制: 128 MB
提交: 33 解决: 11
[提交] [状态] [讨论版] [命题人:admin]题目描述
Dove和Cicada是好朋友，他们经常在一起打扑克来消遣时光，但是他们打的扑克有不同的玩法。
最开始时，牌桌上有n个牌堆，每个牌堆有且仅有一张牌，第i个牌堆里那个扑克牌的编号为i，任意两张牌仅有标号不同。游戏会进行m轮，每轮Dove可以执行下列操作之一：
·1 x y，将编号为x,y的牌所在的牌堆合并，如果此时x,y已在同一牌堆中，那么不进行任何操作。
·2 c，询问有多少对牌堆的牌数之差不少于c。形式化的，对于当前的r个牌堆中，有多少对i,j(i
每次Cicada都不能很快的回答出Dove的询问，为了不让Cicada难堪，Dove想要写一个小程序来帮助Cicada，但是Dove还要学高考，所以这个任务就交给你啦！
输入
第一行两个空格隔开的整数n,m。
接下来m行，每行1 x y或者2 c，具体含义如上文所示。 （n,c≤105，m≤3×105）
输出
对于每个询问，输出一行一个整数表示答案。
样例输入
8 4
2 1
2 2
1 1 1
2 0
样例输出
0
0
28
来源/分类
衡水2018NOIP考前集训
用并查集模拟合并操作，计算小于c的对数，总对数-小于c的对数即为ans
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
ll fa[maxn], cnt[maxn], val[maxn];
ll all;
set num;
ll findd(ll x) {
return fa[x] == x ? x : fa[x] = findd(fa[x]);
}
void uni(ll a, ll b) {
ll p1 = findd(a), p2 = findd(b);
if (p1 != p2) {
cnt[val[p1]]--;
cnt[val[p2]]--;
if (cnt[val[p1]] == 0) num.erase(val[p1]);
if (cnt[val[p2]] == 0) num.erase(val[p2]);
cnt[val[p1] + val[p2]]++;
num.insert(val[p1] + val[p2]);
fa[p2] = p1;
val[p1] += val[p2];
all--;
}
}
void init(ll n) {
cnt[1] = n;
all = n;
num.insert(1);
for (ll i = 1; i <= n; i++) {
fa[i] = i;
val[i] = 1;
}
}
int main() {
freopen("input.txt", "r", stdin);
ll n, m;
scanf("%lld %lld", &n, &m);
init(n);
ll op;
ll x, y;
for (ll i = 0; i scanf("%lld", &op);
if (op == 1) {
scanf("%lld %lld", &x, &y);
uni(x, y);
} else {
scanf("%lld", &x);
set::iterator it, j;
it = num.begin();
j = it;
ll sum = 0;
ll ans = 0;
for (; it != num.end(); it++) {
while (j != num.end() && (*j - *it sum += cnt[*j];
j++;
}
sum -= cnt[*it];
if (x > 0) ans += 1ll * cnt[*it] * (cnt[*it] - 1) / 2;
ans = ans + cnt[*it] * sum;
}
printf("%lld\n", all * (all - 1) / 2 - ans);
}
}
return 0;
}
京公网安备 11010802041100号