题解 P3201 【[HNOI2009]梦幻布丁】

λᴉʍ · 2018-12-26 19:59:28 · 题解

set启发式合并，代码巨短

首先对每个元素维护一个set，变颜色相当于合并一个颜色的set到另一个颜色里去

注意到段数=1+\sum_{i=1}^{n-1}[A_i!=A_{i+1}]，所以维护一下当前的段数，容易看出段数不会减少，当两个相邻的数变成了一样的，以后就都会一样了，段数永久-1

但是暴力合并复杂度不对，所以启发式合并

启发式合并其实就是一个暴力，原理就是把小的合并到大的，每次合并的复杂度只和小的那部分大小有关

这样的话一个元素每被当作小的集合合并一次，所在的集合大小至少\times 2，也就是说只会被合并\log_2n次

注意一下set直接交换是O(n)的，所以要用指针交换。

#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int A[100010];
std::set<int> *q[1000010];
int main(){
    int n=gi(),m=gi(),res=0,opt,x,y;
    for(int i=1;i<=1000000;++i)q[i]=new std::set<int>;
    for(int i=1;i<=n;++i)A[i]=gi(),res+=A[i]!=A[i-1],q[A[i]]->insert(i);
    while(m--){
        opt=gi();
        if(opt==2)printf("%d\n",res);
        else{
            x=gi(),y=gi();if(x==y)continue;
            if(q[x]->size()>q[y]->size())std::swap(q[x],q[y]);
            for(auto i:*q[x])res-=q[y]->count(i-1)+q[y]->count(i+1);
            for(auto i:*q[x])q[y]->insert(i);
            q[x]->clear();
        }
    }
    return 0;
}