题目大意：给一个颜色序列，待修改，求区间颜色段数。
(Solution)
考虑线段树合并。
对于每一个颜色建一个线段树，维护每个颜色出现的位置。同时维护区间的颜色段数，以及最左端、最右端的颜色位置。
于是，对于合并颜色(x,y).，·将它们对应线段树合并即可。合并时，当一树为空时，直接返回；当递归到叶子时，左右均为该处(pos).颜色段为1，返回即可。
对于插入时，与合并处理边界一样。
维护信息时，左端信息优先考虑左子树，右端信息优先考虑右子树，总信息将左右颜色段相加，但若两端相交处颜色相同，则需要-1.
修改时一同维护(ans.)即可。
（蒟蒻第一次写非权值线段树的线段树合并）
( ext{Code:})
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+10;
int n,m,ans;
int rt[MAXN],ch[MAXN<<5][2],rub[MAXN<<5],tot,cnt;
int a[MAXN],ls[MAXN<<5],rs[MAXN<<5],ms[MAXN<<5];
inline int build(){return (cnt?rub[cnt--]:++tot);}
inline void del(int x){
ch[x][0]=ch[x][1]=0;
ls[x]=rs[x]=ms[x]=0;
rub[++cnt]=x;return;
}
inline void pushup(int x){
ls[x]=ls[ch[x][0]]?ls[ch[x][0]]:ls[ch[x][1]];
rs[x]=rs[ch[x][1]]?rs[ch[x][1]]:rs[ch[x][0]];
ms[x]=ms[ch[x][0]]+ms[ch[x][1]]-(rs[ch[x][0]]+1==ls[ch[x][1]]);
}
void modify(int &p,int l,int r,int pos){
if(!p)p=build();
if(l==r){
ls[p]=rs[p]=pos,ms[p]=1;
return;
}
int mid=l+r>>1;
if(pos<=mid)modify(ch[p][0],l,mid,pos);
else modify(ch[p][1],mid+1,r,pos);
pushup(p);
}
int merge(int x,int y,int l,int r){
if(!x||!y){return x+y;}
if(l==r){
ls[x]=rs[x]=l;ms[x]=1;
del(y);return x;
}
int mid=l+r>>1;
ch[x][0]=merge(ch[x][0],ch[y][0],l,mid);
ch[x][1]=merge(ch[x][1],ch[y][1],mid+1,r);
del(y);pushup(x);return x;
}
inline void solve(){printf("%lld
",ans);}
void change(int x,int y){
ans-=ms[rt[x]];ans-=ms[rt[y]];
rt[y]=merge(rt[y],rt[x],1,n);
ans+=ms[rt[y]];rt[x]=0;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
for(int i=1;i<=n;++i){
ans-=ms[rt[a[i]]];
modify(rt[a[i]],1,n,i);
ans+=ms[rt[a[i]]];
}
int Q=m;
for(;Q;Q--){
int opt;
scanf("%lld",&opt);
if(opt==2)solve();
else {
int x,y;
scanf("%lld%lld",&x,&y);
if(x==y)continue;
change(x,y);
}
}
return 0;
}