Description
N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色. Input
第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数. 0 Output
针对第二类操作即询问，依次输出当前有多少段颜色. 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); } } }