【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
链表,启发式合并。
把x变成y,和y全都变成x.
不论是前者还是后者。连续段的个数都是相同的,不影响结果。
那么我们把x,y中出现次数少的变成出现次数多的就好了。
每次只要O(小的数字的个数)就能完成合并。
(扫描一遍所有的'x'所在的位置,看看有没有和y相邻的,有的话,联通数递减)
如果我们每次都遵循这样的规则,那么每次都可以把少的数字的个数最少乘2.
那么最多log2N次就能把全部数字变成一样的了(这时,无论什么操作都能O(1)做完了
那么复杂度就是nlogn的了。
因为有时候是x变成y
但是y比较少
就等价变成y变成x了
但是这个时候,不能认为y没有了
而是应该认为x没有了。
为了避免之后认为y没有了。
我们需要标记一下现在想去找y,就变成找x了。
(因为我们把y变成了x,但实际操作是x变成了y
一开始f[a[i]] = a[i]
那么swap(f[x],f[y])就好
【代码】
#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int N = 1e6;
int n,m,a[N+10],fz[N+10],_size[N+10],ans = 1;
int fir[N+10],nex[N+10];
void _merge(int x,int y){
if (_size[fz[x]]>_size[fz[y]]) swap(fz[x],fz[y]);
x = fz[x],y = fz[y];
if (x==y) return;
if (fir[x]==0) return;
for (int i = fir[x];i;i = nex[i]){
if (i>1 && a[i-1]==y){
ans--;
}
if (i<n && a[i+1]==y){
ans--;
}
}
for (int i = fir[x];i;i = nex[i]){
a[i] = y;
}
int j;
for (j = fir[x];nex[j];j = nex[j]);
nex[j] = fir[y];
fir[y] = fir[x];
fir[x] = 0;
_size[y]+=_size[x];
_size[x] = 0;
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
scanf("%d%d",&n,&m);
rep1(i,1,n) {
scanf("%d",&a[i]);
nex[i] = fir[a[i]];
fir[a[i]] = i;
fz[a[i]] = a[i];
_size[a[i]]++;
}
rep1(i,2,n) if (a[i]!=a[i-1]) ans++;
rep1(i,1,m){
int ope;
scanf("%d",&ope);
if (ope==1){
int x,y;
scanf("%d%d",&x,&y);
_merge(x,y);
}else{
printf("%d\n",ans);
}
}
return 0;
}