自动搬运

查看原文

来自洛谷，原作者为

	cqbzlzm 颓入佳境~

搬运于2025-08-24 22:21:22，当前版本为作者最后更新于2023-08-16 17:08:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

先简单转换一下题意：

Solution

注意到要合并两朵云，所以想到要使用并查集。每朵云就是一个集合，用并查集维护。

我们考虑如何判断一朵云是祥云：

假设一朵云中对应位置的集合上的数$i$的出现次数记为$cnt_i$。比如一朵云上位置上的数为 $1,2,2$，那么 $cnt_1 = 1, cnt_2 = 2$。

对于 $cnt_1,cnt_2 \cdots cnt_n$，我们考虑使用哈希来记录整个数组。

即对于每个并查集维护一个 $H = P^ncnt_n + P^{n - 1}cnt_{n - 1}+...+Pcnt_1+cnt_0$，当然，同样对排完序后云包含的位置上的数值维护一个哈希值，记作 $Hq$。

在合并两个并查集时，我们只需要将两个并查集的原有哈希值相加即可。

完成上述操作后，我们就可以在合并并查集的时候记录祥云数量，这样操作3也解决了。

最后考虑操作4，设有两朵云，哈希值为 $H_1,Hq_1, H_2, Hq_2$。

首先要满足条件——这两朵云都是非祥云，即 $H_1 \neq Hq_1$ 且 $H_2 \neq Hq_2$。

再考虑操作后变成祥云，即 $H_1 + H_2 = Hq_1 + Hq_2$。

移项得：$Hq_1-H_1=-(Hq_2-H_2)$ 且 $Hq_1-H1\neq 0$。

所以我们维护一个 map，下表为 $Hq_1-H_1$，值为满足这个条件的祥云的元素个数和。

这道题到这里就结束了，注意所有操作都是再并查集里面边修改边维护，所以操作很多，现成一个函数会简洁很多。

Code

#include <bits/stdc++.h>
using namespace std;
#define PP 1234577
//#define mod 1000000000000007
#define MAXN 1000000
#define int long long
int Pow[MAXN + 5];
int n, q, gcloud, cloud, ans;
int p[MAXN + 5], qq[MAXN + 5];
int father[MAXN + 5], H[MAXN + 5], Hq[MAXN + 5], Size[MAXN + 5];
map<int, int>mp;
void add(int K, int S) {
	if (K != 0)
		ans = ans + mp[-K] * S;
	mp[K] += S;
	return;
}
void sub(int K, int S) {
	if (K != 0)
		ans = ans - mp[-K] * S;
	mp[K] -= S;
	return;
}
int find(int x) {
	if (father[x] == x)
		return x;
	return father[x] = find(father[x]);
}
void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx == fy)
		return;
	if (H[fx] == Hq[fx]) 
		gcloud --;
	if (H[fy] == Hq[fy]) 
		gcloud --;
	cloud --;
	father[fx] = fy;
	sub(Hq[fx] - H[fx], Size[fx]);
	sub(Hq[fy] - H[fy], Size[fy]);
	H[fy] = (H[fy] + H[fx]) ;
	Hq[fy] = (Hq[fy] + Hq[fx]) ;
	Size[fy] = Size[fx] + Size[fy];
	add(Hq[fy] - H[fy], Size[fy]);
	if (H[fy] == Hq[fy])
		gcloud ++;
	return;
}

signed main() {
	Pow[0] = 1ll;
	for (int i = 1; i <= MAXN; i ++)
		Pow[i] = Pow[i - 1] * PP ;
	scanf("%lld%lld", &n, &q);
	for (int i = 1; i <= n; i ++)
		father[i] = i, Size[i] = 1;
	for (int i = 1; i <= n; i ++)
		scanf("%lld", &p[i]), qq[i] = p[i];
	sort(qq + 1, qq + 1 + n);
	for (int i = 1; i <= n; i ++) {
		H[i] = Pow[p[i]];
		Hq[i] = Pow[qq[i]];
		if (H[i] == Hq[i])
			gcloud++;
		add(Hq[i] - H[i], 1);
		cloud++;
	}
	while (q --) {
		int op, a, b;
		scanf("%lld", &op);
		if (op == 1) {
			scanf("%lld%lld", &a, &b);
			int fx = find(a), fy = find(b);
			if (fx == fy) {
				swap(p[a], p[b]);
				continue;
			}
			if (H[fx] == Hq[fx])
				gcloud --;
			if (H[fy] == Hq[fy])
				gcloud --;
			sub(Hq[fx] - H[fx], Size[fx]);
			sub(Hq[fy] - H[fy], Size[fy]);
			H[fx] = ((H[fx] - Pow[p[a]] + Pow[p[b]])  )  ;
			H[fy] = ((H[fy] - Pow[p[b]] + Pow[p[a]])  )  ;
			swap(p[a], p[b]);
			add(Hq[fx] - H[fx], Size[fx]);
			add(Hq[fy] - H[fy], Size[fy]);
			if (H[fx] == Hq[fx])
				gcloud ++;
			if (H[fy] == Hq[fy])
				gcloud ++;
		}
		if (op == 2) {
			scanf("%lld%lld", &a, &b);
			merge(a, b);
		}
		if (op == 3) {
			if (cloud == gcloud)
				printf("DA\n");
			else
				printf("NE\n");
		}
		if (op == 4) {
			printf("%lld\n", ans);
		}
	}
	return 0;
}