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);
}
}
}