给出一个包含正整数的数组P（p1,…,pn），并假设数组P经过排序后变成数组Q(q1,…,qn)。定义合法替换集合，如果整数对（X，Y）属于合法交换集合，则表示你可以交换数组p中位置X和位置Y的元素。现在有Q个操作（询问），询问分为以下四种类型：
1.交换位置A和位置B的元素 2.将整数对（A，B）加入到合法交换集合 3.询问是否能通过合法交换集合中的操作，将数组P进行排序。（注意：过程中可以以任何顺序执行交换操作，并且每个交换操作可以执行任意多次） 4.定义位置对（A，B）是相连的当且仅当位置A的元素可以仅通过合法交换集合中的操作移动到位置B。
定义所有和位置A相连的位置组成的集合为A的群集。如果对于每一个在A的群集中的位置j，都能通过一系列合法交换集合中的操作使得pj=qj，则称A的群集是良好的。 你需要回答，有多少对不同的位置对（A，B）满足：
a)位置A和位置B是不相连的 b)A的群集和B的群集都不是良好的 c)如果我们将位置对（A，B）加入到合法交换集合中，A的群集将变成良好的。
注意：在计算时，位置对（A，B）和位置对（B，A）被视为不同的位置对。
【输入格式】
第一行两个正整数，N和Q（1<=N, Q<=1,000,000） 第二行包含N个正整数p1，…，pn（1<=p1,…,pn<=1,000,000） 接下来Q行，每行表示一个操作： 每行第一个数字表示操作的种类，（1，2，3或4） 如果操作种类是1或2，后面紧接着两个正整数A，B（1<=A,B<=N）表示位置对（A，B）
【输出格式】
对于每一个询问（种类为3、4的操作），输出一行作为询问的答案。 对于种类为3的询问的答案输出“YES”或“NO”（不包含双引号）。“YES”表示能通过合法交换集合的操作将数组P排序，“NO”则表示不能。 对于种类为4的询问输出，输出一个非负整数表示对应的答案。
【输入样例】
【样例1】 3 5 1 3 2 4 3 2 2 3 4 3
【样例2】 5 5 4 2 1 4 4 3 4 1 1 3 3 4
【样例3】 4 10 2 1 4 3 3 4 1 1 2 3 4 2 2 3 2 1 2 4 2 3 4 3
【输出样例】
【样例1】 1 NO 0 YES
【样例2】 NO 1 YES 0
【样例3】 NO 2 NO 1 3 YES
【样例解释】
【样例解释1】 第一个询问答案是1，因为只有位置对(2,3)符合所有的条件，第二个询问答案是NO，因为交换集合为空，数字2和3没有办法交换到正确位置，在第三次操作后，我们把位置对(2,3)加入到交换集合中，第四次操作(询问)答案为0因为2和3已经相连，第五次操作(询问)答案是YES，因为可以通过位置对(2,3)把数组排好序。
【数据范围】
50%的数据满足N,Q<=1000。
【来源】
https://jzoj.net
这道题一看就知道是并查集，但具体怎么做就难了。 要定义一个哈希函数，来不重复的代表每个数的权值。 然后定义2个数组。 q（i）表示P中i这个并查集所代表的位置的元素的权值和。 p（i）表示Q中i这个并查集所代表的位置的元素的权值和。 然后用map存每个p(i)-q(i)的值。 当我们要找互相配合起来和谐的并查集时就直接找2个差值加起来为0的就可以了，在中间边变化边记录就好。 而要全部和谐就得所有差值都为0，直接看map中为0的个数是不是n个就可以了。 其他就是并查集了。
具体代码如下：
#include<cstdlib> #include<cstring> #include<cstdio> #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long ll; const int maxn=1000005; const ll mod=2000005ll; ll q[maxn],p[maxn],a[maxn]; map<ll,int>mp; int n,m,b[maxn],pa[maxn],c[maxn]; int num=0,size[maxn]; int find(int x){return pa[x]==x?x:pa[x]=find(pa[x]);} void un(int x,int y) { int px=find(x),py=find(y); if(px==py) return; mp[p[px]-q[px]]-=size[px]; if(q[px]-p[px]!=0) num-=size[px]*mp[q[px]-p[px]]; mp[p[py]-q[py]]-=size[py]; if(q[py]-p[py]!=0)num-=size[py]*mp[q[py]-p[py]]; q[px]+=q[py]; p[px]+=p[py]; size[px]+=size[py]; if(q[px]-p[px]!=0) num+=size[px]*mp[q[px]-p[px]]; mp[p[px]-q[px]]+=size[px]; pa[py]=px; } int read() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); n=read();m=read(); a[1]=17; for(int i=2;i<=1000000;i++) { a[i]=(a[i-1]*17)%mod; } int x,id,y,px,py; for(int i=1;i<=n;i++) { c[i]=b[i]=read(); q[i]=a[b[i]]; pa[i]=i; size[i]=1; } sort(b+1,b+1+n); for(int i=1;i<=n;i++) { p[i]=a[b[i]]; if(q[i]-p[i]!=0)num+=mp[q[i]-p[i]]; mp[p[i]-q[i]]++; } while(m--) { id=read(); if(id==1) { x=read();y=read(); px=find(x),py=find(y); if(px==py) { swap(c[x],c[y]); continue; } mp[p[px]-q[px]]-=size[px]; if(q[px]-p[px]!=0) num-=size[px]*mp[q[px]-p[px]]; mp[p[py]-q[py]]-=size[py]; if(q[py]-p[py]!=0)num-=size[py]*mp[q[py]-p[py]]; q[px]+=a[c[y]]-a[c[x]]; q[py]+=a[c[x]]-a[c[y]]; mp[p[px]-q[px]]+=size[px]; if(q[px]-p[px]!=0)num+=size[px]*mp[q[px]-p[px]]; mp[p[py]-q[py]]+=size[py]; if(q[py]-p[py]!=0)num+=size[py]*mp[q[py]-p[py]]; swap(c[x],c[y]); } if(id==2) { x=read();y=read(); un(x,y); } if(id==3) { if(mp[0]==n) printf("YES\n"); else printf("NO\n"); } if(id==4) { printf("%d\n",num); } } return 0; }