题解：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)

的。

代码

场上写的双哈希，很长。

奇丑无比，不建议阅读

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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