梦幻布丁 启发式合并板子

//题意：将一段布丁染色，然后有两种操作，操作1将颜色为x的布丁全部染为y，操作2统计当前一共有多少段颜色
//思路：将x染色为y可以想到启发式合并，但是注意我们交换大小集合后，有可能最后合并本来应该剩下y集合的，但是却剩下了x集合
//      好在答案与你到底是x还是y无关（只统计颜色段数），只需要在叫到y的时候，将x（或y）合并到另一种颜色就好
#include<bits/stdc++.h>
using namespace std;
const int N = 101000;
const int M = 1010000;
vector<int> pos[M];
int n, m, a[N], ans;
void modify(int p, int col) {
        ans -= (a[p] != a[p - 1]) + (a[p] != a[p + 1]);
    a[p] = col;
        ans += (a[p] != a[p - 1]) + (a[p] != a[p + 1]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pos[a[i]].push_back(i);//将每个位置归类进每个颜色集合
    }
    for (int i = 1; i <= n + 1; i++) ans += a[i] != a[i - 1];//统计不同颜色段数，因为算上了a[0],
                                                         //所以最终ans应该-1
    for (int i = 0; i < m; i++) {
        int op; scanf("%d", &op);
        if (op == 2) printf("%d\n", ans - 1);
        else {
            int x, y;
            scanf("%d%d", &x, &y);
            if (x == y) continue;
            if (pos[x].size() > pos[y].size()) swap(pos[x], pos[y]);//保证x为小集合，最后合并剩下到的集合一定是y
            
            if (pos[y].empty()) continue;
            int col = a[pos[y][0]];//查询集合y中的实际颜色

            for (int p : pos[x]) {
                modify(p, col);//因为pos[y]集合中的点颜色不一定是y，所以需要单独修改
                pos[y].push_back(p);//集合合并
            }
                
            pos[x].clear();

        }
    }
}