题解：P6498 [COCI 2016/2017 #2] Zamjene

· · 题解

noip 模拟赛 T2，场上写了 5.1k，恐怖如斯。

嘱以题解以记之。

思路

先抛出一个问题，怎么快速判断两个可重集合是否相同？

一个简单的思路，就是把一个可重集 S 映射到一个数 x 上，然后直接判断两个映射后的 x 是否相同即可，这是哈希思想。

如果此时还想要进行合并可重集的操作怎么办？这就要求我们的哈希方法必须是可合并的，于是我们就能得到一个简单的思路，随机赋权后和哈希。

我们设 S 的哈希值为 H(S)，设 f(x) 为把 x 映射到值域内任意数的随机映射，则 H 函数可被定义为：

H(S)=\sum_{x\in S}f(x)

其显然满足可加性，即：

H(A+B)=H(A)+H(B)

当然，考虑到哈希冲突，我们可以双哈希。

回到这一题，对于一朵「祥云」，显然等价于关于 p 的可重集与关于 q 的可重集相同，直接采取上述策略即可。

最后考虑操作四。假设 a 所在的「云」关于 p 和关于 q 的可重集的哈希值分别为 (x_1,y_1)，b 所在的「云」关于 p 和关于 q 的可重集的哈希值分别为 (x_2,y_2)，则相当于要求：

x_1\ne y_1\\x_2\ne y_2\\x_1+x_2=y_1+y_2

对最底下的式子移项，得到：

x_1-y_1=y_2-x_2

用并查集维护一下每个「云」的大小，然后把 y_1-x_1 丢进 unordered_map 里维护即可。

综上，时间复杂度是 O(q\log n) 的。

代码

场上写的双哈希，很长。

:::success[奇丑无比，不建议阅读]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <unordered_map>
#define ll long long
using namespace std;
const ll N=1e6+10;
ll rd1[N],rd2[N],n,q,a[N];
ll fa[N],sorted[N];
ll siz[N];
pair<ll,ll> dat1[N],dat2[N];
struct pair_hash{
    template<class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1^(h2<<1);
    }
};
inline ll findf(ll x){
    while(x^fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
unordered_map<pair<ll,ll>,ll,pair_hash> mp;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    srand(114514);
    for(ll i=1;i<=n;i++){
        cin>>a[i];fa[i]=i;
        sorted[i]=a[i];
    }
    for(ll i=1;i<N;i++){
        rd1[i]=rand()*rand();
        rd2[i]=rand()*rand();
    }
    sort(sorted+1,sorted+1+n);
    ll nans=0,cnt=0,clc=n,minu=0;
    for(ll i=1;i<=n;i++){
        siz[i]=1;
        dat1[i].first=rd1[a[i]];
        dat1[i].second=rd1[sorted[i]];
        dat2[i].first=rd2[a[i]];
        dat2[i].second=rd2[sorted[i]];
        if(dat1[i].first==dat1[i].second&&dat2[i].first==dat2[i].second){
            cnt++;
            minu+=mp[make_pair(rd1[a[i]]-rd1[sorted[i]],rd2[a[i]]-rd2[sorted[i]])];
        }   
            nans+=mp[make_pair(rd1[a[i]]-rd1[sorted[i]],rd2[a[i]]-rd2[sorted[i]])];
        mp[make_pair(rd1[sorted[i]]-rd1[a[i]],rd2[sorted[i]]-rd2[a[i]])]++;
    }
    while(q--){
        ll opt,x,y,fx,fy;
        cin>>opt;
        if(opt==1){
            cin>>x>>y;
            fx=findf(x),fy=findf(y);
            if(fx!=fy){
                mp[make_pair(dat1[fx].second-dat1[fx].first,dat2[fx].second-dat2[fx].first)]-=siz[fx];
                if(dat1[fx].first==dat1[fx].second&&dat2[fx].first==dat2[fx].second){
                    cnt--;
                    minu-=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                }
                nans-=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                dat1[fx].first+=rd1[a[y]]-rd1[a[x]];
                dat2[fx].first+=rd2[a[y]]-rd2[a[x]];
                    nans+=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                if(dat1[fx].first==dat1[fx].second&&dat2[fx].first==dat2[fx].second){
                    cnt++;
                    minu+=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                }
                mp[make_pair(dat1[fx].second-dat1[fx].first,dat2[fx].second-dat2[fx].first)]+=siz[fx];

                fx=fy;

                mp[make_pair(dat1[fx].second-dat1[fx].first,dat2[fx].second-dat2[fx].first)]-=siz[fx];
                if(dat1[fx].first==dat1[fx].second&&dat2[fx].first==dat2[fx].second){
                    cnt--;
                    minu-=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                }
                nans-=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                dat1[fx].first+=rd1[a[x]]-rd1[a[y]];
                dat2[fx].first+=rd2[a[x]]-rd2[a[y]];
                    nans+=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                if(dat1[fx].first==dat1[fx].second&&dat2[fx].first==dat2[fx].second){
                    cnt++;
                    minu+=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                }
                mp[make_pair(dat1[fx].second-dat1[fx].first,dat2[fx].second-dat2[fx].first)]+=siz[fx];
            }
            swap(a[x],a[y]);
        }
        if(opt==2){
            cin>>x>>y;
            fx=findf(x),fy=findf(y);
            if(fx!=fy){
                clc--;
                mp[make_pair(dat1[fx].second-dat1[fx].first,dat2[fx].second-dat2[fx].first)]-=siz[fx];
                if(dat1[fx].first==dat1[fx].second&&dat2[fx].first==dat2[fx].second){
                    cnt--;
                    minu-=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                }
                nans-=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];

                mp[make_pair(dat1[fy].second-dat1[fy].first,dat2[fy].second-dat2[fy].first)]-=siz[fy];
                if(dat1[fy].first==dat1[fy].second&&dat2[fy].first==dat2[fy].second){
                    cnt--;
                    minu-=siz[fy]*mp[make_pair(dat1[fy].first-dat1[fy].second,dat2[fy].first-dat2[fy].second)];
                }
                nans-=siz[fy]*mp[make_pair(dat1[fy].first-dat1[fy].second,dat2[fy].first-dat2[fy].second)];

                fa[fy]=fx;
                dat1[fx].first+=dat1[fy].first;
                dat1[fx].second+=dat1[fy].second;
                dat2[fx].first+=dat2[fy].first;
                dat2[fx].second+=dat2[fy].second;
                siz[fx]+=siz[fy];
                    nans+=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                if(dat1[fx].first==dat1[fx].second&&dat2[fx].first==dat2[fx].second){
                    cnt++;
                    minu+=siz[fx]*mp[make_pair(dat1[fx].first-dat1[fx].second,dat2[fx].first-dat2[fx].second)];
                }
                mp[make_pair(dat1[fx].second-dat1[fx].first,dat2[fx].second-dat2[fx].first)]+=siz[fx];
            }
        }
        if(opt==3){
            if(cnt==clc) cout<<"DA\n";
            else cout<<"NE\n"; 
        } 
        if(opt==4){
            cout<<nans-minu<<"\n";
        }
    }
    return 0;
}

:::