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

題解

用鏈表來更好的遍歷每種顏色 暴力遍歷算對答案的貢獻 合并時用啟發式合并 就是如果s[b]<s[a] 就把b和入a 但是把a和b真實對應的顏色改一下(很常用的技巧) 那么對于最不好的情況 也就是每次s[b]=s[a] 合并時 s擴大logn次 如果把同一個s級別的一起看 每次O(n) 所以最壞時間復雜度O(nlogn) 雖然這道題不用啟發式合并速度也差不多(但就要注意b為空的情況了 啟發式合并可以直接避免) 再次記一下合并鏈表步驟(合a入b) next[b尾]=a首；b首=a首；清空a；

代碼

#include<cstdio> #include<algorithm> using namespace std; const int N=1e5+5,M=1e6+5;int c[N],next[N],head[M],last[M],p[M],s[M]; int n,m,ans;int solve(int a,int b){s[b]+=s[a];s[a]=0;for(int i=last[a];i;i=next[i]){if(c[i-1]==b) ans--;if(c[i+1]==b) ans--;}for(int i=last[a];i;i=next[i]) c[i]=b;next[head[b]]=last[a];head[b]=head[a];last[a]=head[a]=0; }int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&c[i]);p[c[i]]=c[i];s[c[i]]++;if(c[i]!=c[i-1]) ans++;if(!last[c[i]]) head[c[i]]=i;next[i]=last[c[i]];last[c[i]]=i;}int x,a,b;for(int i=1;i<=m;i++){scanf("%d",&x);if(x==1){scanf("%d%d",&a,&b);if(a==b) continue;if(s[p[a]]>s[p[b]]) swap(p[a],p[b]);a=p[a];b=p[b];if(!s[a]) continue;solve(a,b);}else printf("%d\n",ans);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/xkui/p/4535512.html

總結

以上是生活随笔為你收集整理的【链表+启发式合并】Bzoj1483 [HNOI2009] 梦幻布丁的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。