Description

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜***r> Input

第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数. 0
Output

针对第二类操作即询问，依次输出当前有多少段颜***r> Sample Input
4 3

1 2 2 1

2

1 2 1

2

Sample Output
3

1

题目数据范围没给，随手开了1000000数组

考虑一下暴力合并的复杂度显然是O(n*m)，显然不可取

那么考虑一下启发式合并O(nlogn)

我们可以把一个颜色对应的所有位置挂成链。

每一次合并暴力添加链。

就很方便找位置了。

另外，为了实现启发式合并，我们需要记录每一种颜色当前代表哪一种颜色。

第一种是链表启发式合并： 488msAC

///BZOJ 1483
///链表启发式合并

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n, m, cnt, color[maxn], curcolor[maxn], head[maxn], sum[maxn], ans;
struct node{int u,v,next;}E[maxn*4];
void add(int u, int v){E[cnt].u=u,E[cnt].v=v,E[cnt].next=head[u], head[u]=cnt++;}
void init(){memset(head,-1,sizeof(head)); cnt=0;}
int main(){
    init();
    scanf("%d%d", &n,&m);
    for(int i=1; i<=n; i++){
        scanf("%d", &color[i]);
        if(color[i]!=color[i-1]) ans++;
        sum[color[i]]++;
        curcolor[color[i]]=color[i];
        add(color[i],i);
    }
    for(int i=1; i<=m; i++){
        int op;
        scanf("%d", &op);
        if(op==1){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y) continue;
            if(sum[curcolor[x]]>sum[curcolor[y]]) swap(curcolor[x], curcolor[y]);
            int fx=curcolor[x],fy=curcolor[y];
            if(sum[fx]==0) continue;
            for(int i=head[fx]; i+1; i=E[i].next){
                int v=E[i].v;
                if(color[v+1]==fy) ans--;
                if(color[v-1]==fy) ans--;
            }
            for(int i=head[fx]; i+1; i=E[i].next){
                color[E[i].v]=fy, add(fy,E[i].v);
            }
            head[fx]=-1,sum[fy]+=sum[fx],sum[fx]=0;
        }
        else{
            printf("%d\n", ans);
        }
    }
    return 0;
}

第二种平衡树启发式合并，直接用set，常数比较大

908ms AC

///BZOJ 1483

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n, m, ans;
int color[maxn], curcolor[maxn];
set <int> t[maxn];
void solve(int a, int b){
    set<int>::iterator it;
    for(it = t[a].begin(); it!=t[a].end(); it++){
        if(color[*it-1]==b) ans--;
        if(color[*it+1]==b) ans--;
        t[b].insert(*it);
    }
    for(it = t[a].begin(); it!=t[a].end(); it++) color[*it]=b;
    t[a].clear();
}
int main(){
    scanf("%d%d", &n,&m);
    for(int i=1; i<=n; i++) scanf("%d", &color[i]);
    for(int i=1; i<=n; i++){
        curcolor[color[i]]=color[i];
        if(color[i]!=color[i-1]) ans++;
        t[color[i]].insert(i);
    }
    for(int i=1; i<=m; i++){
        int op;
        scanf("%d", &op);
        if(op==2) printf("%d\n", ans);
        else{
            int a, b; scanf("%d%d", &a,&b);
            if(a==b) continue;
            if(t[curcolor[a]].size()>t[curcolor[b]].size()) swap(curcolor[a],curcolor[b]);
            a=curcolor[a], b=curcolor[b];
            solve(a,b);
        }
    }
}