Evanyou Blog 彩带

梦幻布丁

题目描述

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

输入输出格式

输入格式：

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

输出格式：

针对第二类操作即询问，依次输出当前有多少段颜色.

输入输出样例

输入样例#1：

输出样例#1：

3
1

说明

1<=n,m<=100,000; 0<Ai,x,y<1,000,000

　　分析：

　　是一道interesting的题目。

　　一开始打了个线段树，然后就被愉快的T飞了。卡常也只能过5个点。

　　正解是链表+启发式合并，把这个同种颜色的布丁造成链表维护，修改的时候直接修改。当然，直接修改的话效率还是稍低，那么就用到启发式合并。因为实际上它修改成什么颜色并不重要，重要的是有多少个颜色区间，那么修改的时候就可以从这里下手，每次都修改数量更少的那个颜色，这样子的效率就非常优秀了（完虐线段树）。

　　Code：

//It is made by HolseLee on 27th July 2018
//Luogu.org P3201
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;

const int N=1e5+7;
const int M=1e6+7;
int n,m,ans,a[N],head[M],nxt[N],fir[M],pre[M],sum[M];

int read()
{
    char ch=getchar();int num=0;
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        num=(num<<3)+(num<<1)+ch-'0';ch=getchar();
    }
    return num;
}

void change(int x,int y)
{
    for(int i=head[x];i!=-1;i=nxt[i]){
        ans-=(a[i+1]==y?1:0);
        ans-=(a[i-1]==y?1:0);
    }
    for(int i=head[x];i!=-1;i=nxt[i])a[i]=y;
    nxt[fir[x]]=head[y];
    head[y]=head[x];
    sum[y]+=sum[x];
    head[x]=-1;sum[x]=fir[x]=0;
}


int main()
{
    n=read();m=read();
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;++i){
        a[i]=read();
        pre[a[i]]=a[i];
        sum[a[i]]++;
        if(a[i]!=a[i-1])ans++;
        if(head[a[i]]==-1)fir[a[i]]=i;
        nxt[i]=head[a[i]];
        head[a[i]]=i;
    }
    int op,x,y;
    for(int i=1;i<=m;++i){
        op=read();
        if(op==1){
            x=read();y=read();
            if(x==y)continue;
            if(sum[pre[x]]>sum[pre[y]])swap(pre[x],pre[y]);
            x=pre[x],y=pre[y];
            if(sum[x]==0)continue;
            change(x,y);
        }
        else printf("%d
",ans);
    }
    return 0;
}