50pts求条

#include<iostream>
using namespace std;
long long n,m;
long long la[1000006];
long long l[2000006],r[2000006],sum[2000006],lx[2000006],rx[2000006];
long long t,rt[2000006];
void pu(long long p,long long a,long long b){
	lx[p]=lx[l[p]],rx[p]=rx[r[p]];
	sum[p]=sum[l[p]]+sum[r[p]];
	if(rx[l[p]]&&lx[r[p]]){
		sum[p]--;
	}
}
void js(long long a,long long b,long long x){
	t++;
	long long p=t;
	if(a==b){
		sum[p]=lx[p]=rx[p]=1;
		return ;
	}
	long long g=(a+b)>>1;
	if(g>=x){
		l[p]=t+1;
		js(a,g,x);
	}else{
		r[p]=t+1;
		js(g+1,b,x);
	}
	pu(p,a,b);
	return ;
}
long long hb(long long x,long long y,long long a,long long b){
	if(!x||!y)return x+y;
	if(a==b){
		sum[x]+=sum[y];
		lx[x]+=lx[y];
		rx[x]+=rx[y];
		return x;
	}
	long long g=(a+b)>>1;
	l[x]=hb(l[x],l[y],a,g);
	r[x]=hb(r[x],r[y],g+1,b);
	pu(x,a,b);
	return x;
}
long long ans;
int main(){
	freopen("D_7.in","r",stdin);
	freopen("D.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		long long pyj;
		scanf("%lld",&pyj);
		rt[i]=t+1;
		js(1,n,i);
		ans++;
		if(la[pyj]){
			ans-=sum[rt[i]]+sum[rt[la[pyj]]];
			rt[la[pyj]]=hb(rt[la[pyj]],rt[i],1,n);
			ans+=sum[rt[la[pyj]]];
		}
        else{
            la[pyj]=i;
        }
	}
	while(m--){
		long long k;
		scanf("%lld",&k);
		if(k==1){
			long long x,y;
			scanf("%lld%lld",&x,&y);
			long long f1=la[x],f2=la[y];
            if(rt[f2]==0){
                rt[f2]=rt[f1];
                rt[f1]=0;
                continue;
            }
			if(f1!=f2){
				ans-=sum[rt[f1]]+sum[rt[f2]];
				rt[f2]=hb(rt[f2],rt[f1],1,n);
				ans+=sum[rt[f2]];
                rt[f1]=0;
			}
		}else{
			printf("%lld\n",ans);
		}
	}
	return 0;
}