（畫師當然是武內崇啦）

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

最近在復習數據結構，本來打算找一道平衡樹的題來做，在黃學長的博客里看到這道題。結果發現和平衡樹其實沒有關系。。。

看到這個題的第一想法是暴力：每次o(n)修改或查詢
然而o(n^2)肯定會爆（雖然題目不給范圍神坑）。我們希望能夠通過某些手段來降log。首先是想到線段樹，因為線段樹可以解決區間內連續色段，但是我們發現這道題是針對整個序列而言，且修改無法用線段樹優化。

那怎么辦呢？我們發現這道題是將所有顏色為x的改為y，總共有效的修改數量是初始時的顏色種數（最多n）。其實這相當于將顏色x與顏色y合并，且之后不會再拆開。所以說這就是合并的問題啦~（廢話了這么久。。）

但是該如何合并呢？我們將同一種顏色的布丁用鏈表連起來，合并的時候是o(1)的。但是對于合并時ans的更新是o(n)的（對于每一個都判斷修改后是否與左右連接）。總的來說，就是每次合并時的復雜度“被修改的顏色的布丁個數”。

這個是可以優化的，就是用啟發式合并（把小的往大的合并）。這樣就是o(nlogn)的了。證明就搬一下黃學長的；

1：每次O(N)
2：每次合并后，隊列長度一定大于等于原來短的長度的兩倍。
這樣相當于每次合并都會讓短的長度擴大一倍以上，
最多擴大logN次，所以總復雜度O(NlogN)，每次O(logN)。

但是由于為了啟發式合并，我們改變了合并方向。需要用一個f[i]數組來存 調用i顏色時真正用到的顏色。

下面談談鏈表：
我以前一直都不清楚鏈表到底是個什么貨。現在好像是明白了：
有兩種鏈表：
1、對于每個點，有一個pre（前繼）和nxt（后繼）。這相當于雙向鏈表
2、記錄一個鏈表的開頭head，對每個點記錄一個nxt（下一個）。這相當于是單向鏈表

這道題需要訪問鏈表的全部元素，所以用第二種鏈表。

（其實之前接觸過這鏈表很多次，但一直不知道這就是鏈表）

放代碼啦：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int N=1000000+5;int n,m,c[N],siz[N],f[N],ans=0; int head[N],nxt[N],st[N];void solve(int a,int b){for(int i=head[a];i;i=nxt[i]){if(c[i+1]==b) ans--;if(c[i-1]==b) ans--;}for(int i=head[a];i;i=nxt[i]) c[i]=b;/*這是兩種不同的合并方式*/ // nxt[st[a]]=head[b];head[b]=head[a];nxt[st[b]]=head[a]; // head[a]=0,st[a]=0;st[b]=st[a]; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&c[i]);siz[c[i]]++,f[c[i]]=c[i];if(c[i]!=c[i-1]) ans++;if(!head[c[i]]) st[c[i]]=i;nxt[i]=head[c[i]],head[c[i]]=i;}int opt,x,y;while(m--){scanf("%d",&opt);if(opt==2) printf("%d\n",ans);else{scanf("%d%d",&x,&y);if(x==y) continue;//if(siz[f[x]]==0) continue;if(siz[f[x]]>siz[f[y]]) swap(f[x],f[y]);if(siz[f[x]]==0) continue;siz[f[x]]+=siz[f[y]],siz[f[x]]=0;//+=solve(f[x],f[y]);}}return 0; }

轉載于:https://www.cnblogs.com/LinnBlanc/p/7763119.html

總結

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

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