题意简化:
n个布丁,有m个颜色
操作:
op1:要把一个颜色的布丁全部变为另一种颜色
op2:询问连续的颜色段个数
解题方法:
算法:启发式合并 (集合合并的优化)
统计不同颜色段数:
初始就直接扫描,每一次合并一个颜色的布丁全部变为另一种颜色,本质是将他们合并为同一类
维护合并段数:
颜色段数一定不会增加,遍历一下看所有的这个颜色的布丁,然后看他左右两边的颜色来维护段数
合并:
当x要合并到y
问题:合并颜色有可能与题目的操作不对应
if x<=y 那么合并就可以
else x>y y就要合并到x
解决方法:
用一个数组表示 所有颜色
用一个单链表示 颜色的编号,然后让他们来合并布丁
实现时我们就要改变映射,例如:x--1 y--2 : x-->y : x-->2 y-->1 这样就可以解决x-->y颜色的问题
时间复杂度:O(nlogn)
由于每一个点合并时间O(1),合并次数O(nlogn)
代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1000010,M=1000010; // 节点 操作数
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qmi(ll m,ll k, ll p=mod){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;}
ll inv(ll a){return qmi(a,mod-2);}
int n,m;
int h[M],e[N],ne[N],idx; //单链表五剑客
int color[N],sz[M],p[M]; // 颜色 大小 映射
int ans;
// 单链表常用函数 !!!
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
sz[a]++;
}
void merge(int& x,int &y){
if(x==y)return;
if(sz[x]>sz[y])swap(x,y);
//段数更新
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
ans-=(color[j-1]==y)+(color[j+1]==y);
}
//合并
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
color[j]=y;
// 头插法
if(ne[i]==-1){
ne[i]=h[y],h[y]=h[x];
break;
}
}
h[x]=-1;//清空;
sz[y]+=sz[x],sz[x]=0;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
scanf("%d",&color[i]);
if(color[i]!=color[i-1])ans++; //如果与前面不同
add(color[i],i); //添加到这个颜色下面
}
//初始化映射
for(int i=0;i<M;i++)p[i]=i;
while(m--){
int op;scanf("%d",&op);
if(op==2)printf("%d\n",ans);
else {
int x,y;scanf("%d%d",&x,&y);
merge(p[x],p[y]);
}
}
return 0;
}