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