[COCI2016-2017#2] Zamjene 题解

cqbzlzm · 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;
}