3201 [HNOI2009]梦幻布丁

题目描述

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

输入输出格式

输入格式：

第一行给出\(N,M\)表示布丁的个数和好友的操作次数. 第二行\(N\)个数\(A_1,A_2,\dots,A_n\)表示第\(i\)个布丁的颜色.

从第三行起有\(M\)行,对于每个操作,若第一个数字是\(1\)表示要对颜色进行改变，其后的两个整数\(X,Y\)表示将所有颜色为\(X\)的变为\(Y\)，\(X\)可能等于\(Y\).

若第一个数字为\(2\)表示要进行询问当前有多少段颜色，这时你应该输出一个整数.

输出格式：

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

说明

\(1<=n,m<=100,000,0<A_i,x,y<1,000,000\)

---

思路：对每个颜色维护一个平衡树，平衡树每个节点维护一个是否贡献，我设定的是与前驱是否相邻，然后维护子树贡献和。每次暴力启发式合并就可以了。

听说有链表\(O(n\log n)\)的高级做饭，但是我懒得看。

---

Code:

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#define ls ch[now][0]

#define rs ch[now][1]

const int N=1e5+10;

int sum[N],ch[N][2],val[N],d[N],siz[N],root[N*10],n,m;

void updata(int now){sum[now]=sum[ls]+sum[rs]+d[now],siz[now]=siz[ls]+siz[rs]+1;}

void split(int now,int k,int &x,int &y)

{

    if(!now){x=y=0;return;}

    if(now<=k)

        x=now,split(rs,k,rs,y);

    else

        y=now,split(ls,k,x,ls);

    updata(now);

}

int Merge(int x,int y)

{

    if(!x||!y) return x|y;

    if(val[x]<val[y])

    {

        ch[x][1]=Merge(ch[x][1],y);

        updata(x);

        return x;

    }

    else

    {

        ch[y][0]=Merge(x,ch[y][0]);

        updata(y);

        return y;

    }

}

void Insert(int id,int now)

{

    int x,y,z;

    split(root[id],now,x,y);

    split(x,now-2,x,z);

    sum[now]=d[now]=z==0;

    x=Merge(x,z);

    split(y,now+1,z,y);

    sum[z]=d[z]=0;

    y=Merge(z,y);

    root[id]=Merge(x,Merge(now,y));

}

void dfs(int id,int now)

{

    if(!now) return;

    dfs(id,ls),dfs(id,rs);

    ls=rs=0,siz[now]=1,Insert(id,now);

}

int ans=0;

void merge(int x,int y)

{

    if(x==y) return;

    if(siz[root[x]]<siz[root[y]]) std::swap(root[x],root[y]);

    ans-=sum[root[x]]+sum[root[y]];

    dfs(x,root[y]);

    root[y]=0,ans+=sum[root[x]];

}

int main()

{

    //freopen("data.in","r",stdin);

    //freopen("dew.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int clo,i=1;i<=n;i++)

    {

        scanf("%d",&clo);

        val[i]=rand(),siz[i]=1;

        Insert(clo,i);

    }

    for(int i=1;i<=1000000;i++) ans+=sum[root[i]];

    for(int op,x,y,i=1;i<=m;i++)

    {

        scanf("%d",&op);

        if(op==1) scanf("%d%d",&x,&y),merge(y,x);

        else printf("%d\n",ans);

    }

    return 0;

}

---

2018.12.12