Brief description:
略。）
Analysis:
启发式合并 + 链表）
（。。如果手写链表的话。。可以删去中间已经没用的格子。。只保留联通块左右？。）
//}/* .................................................................................................................................. */
const int N = int(1e5) + 9, M = int(1e6) + 9;
int a[N], p[M]; VI adj[M];
int n, m, z;
#define px p[x]
#define py p[y]
void Merge(){
int x, y; RD(x, y); if (x == y) return; //if (px == py) return;
if (!px) return;
if (!py){
py = px;
px = 0;
return;
}
if (SZ(adj[px]) > SZ(adj[py])) swap(px, py);
ECH(it, adj[px]){
if (a[*it-1] == py) --z;
if (a[*it+1] == py) --z;
adj[py].PB(*it);
}
ECH(it, adj[px]) a[*it] = py;
CLR(adj[px]); px = 0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n, m); REP_1(i, n){
adj[RD(a[i])].PB(i), p[a[i]] = a[i];
if (a[i] != a[i-1]) ++z;
}
DO(m){
if (RD() == 1){
Merge();
}
else{
OT(z);
}
}
}
