題目描述
N個布丁擺成一行,進行M次操作.每次將某個顏色的布丁全部變成另一種顏色的,然后再詢問當前一共有多少段顏色.例如顏色分別為1,2,2,1的四個布丁一共有3段顏色.
第一行給出N,M表示布丁的個數和好友的操作次數. 第二行N個數A1,A2...An表示第i個布丁的顏色從第三行起有M行,對于每個操作,若第一個數字是1表示要對顏色進行改變，其后的兩個整數X,Y表示將所有顏色為X的變為Y，X可能等于Y. 若第一個數字為2表示要進行詢問當前有多少段顏色，這時你應該輸出一個整數.?
Solution
膜了一發hzwer。
我們對于每一種顏色，開鄰接表，把它搞成一個隊列的形式，開一個數組記錄它的開頭。
對于一個修改，我們采用啟發式合并的方式，可以把均攤復雜度將至llogn。
合并兩個隊列的方式就是把第一個隊列接到第二個隊列后面就可以了。
e[st[x]]=head[y];head[y]=head[x];就是這樣
為了避免啟發式合并之后顏色出現錯亂if(!st[a[i]])st[a[i]]=i;if(size[ji[x]]>size[ji[y]])swap(ji[x],ji[y]);x=ji[x];y=ji[y];
Code
#include<iostream> #include<cstdio> #define NN 1000002 #define N 100002 using namespace std; int head[NN],ans,size[NN],e[N<<1],a[N],n,m,x,y,st[NN],ji[NN]; inline void solve(int x,int y){for(int i=head[x];i;i=e[i]){if(a[i+1]==y)ans--;if(a[i-1]==y)ans--; }for(int i=head[x];i;i=e[i])a[i]=y;size[y]+=size[x];e[st[x]]=head[y];head[y]=head[x];size[x]=0; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){scanf("%d",&a[i]);ji[a[i]]=a[i];if(!st[a[i]])st[a[i]]=i;if(a[i]!=a[i-1])ans++;e[i]=head[a[i]];head[a[i]]=i;size[a[i]]++;}for(int i=1;i<=m;++i){scanf("%d",&x);if(x==2)printf("%d\n",ans);else{scanf("%d%d",&x,&y);if(x==y)continue;if(size[ji[x]]>size[ji[y]])swap(ji[x],ji[y]);x=ji[x];y=ji[y];if(size[x]==0)continue;solve(x,y);}}return 0; }
?
