bzoj1483[HNOI2009]夢幻布丁

bzoj1483[HNOI2009]夢幻布丁

題意：

N個布丁擺成一行,進行M次操作.每次将某個顔色的布丁全部變成另一種顔色的,然後再詢問目前一共有多少段顔色。

題解：

給每個顔色建一個連結清單。先預處理出答案，然後每次修改顔色時将兩個連結清單合并，同時将修改後顔色對答案的貢獻重新計算（如果兩個節點的位置相差大于1說明中間有一段顔色，将貢獻+1）。連結清單合并時用啟發式合并（就是将小的拆了依次插入到大的裡面），複雜度O(nlog2n)（均攤複雜度，玄學）。

代碼：

1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define M 1000010
 6 #define N 100010
 7 using namespace std;
 8 
 9 int ans,head[M],last[N],next[N],comb[M],sz[M],n,m;
10 int main(){
11     scanf("%d",&n); scanf("%d",&m); int a,b=0; ans=0; 
12     memset(sz,0,sizeof(sz)); memset(comb,0,sizeof(comb)); memset(head,0,sizeof(head));
13     inc(i,1,n){
14         scanf("%d",&a); if(a!=b)ans++,comb[a]++;
15         next[i]=head[a]; last[head[a]]=i; head[a]=i; sz[a]++; b=a;
16     }
17     inc(i,1,m){
18         int a1; scanf("%d",&a1); if(a1==2)printf("%d\n",ans);
19         if(a1==1){
20             int a2,a3; scanf("%d%d",&a2,&a3); if(a2==a3)continue;
21             if(head[a2]==0)continue; 
22             else if(head[a3]==0)head[a3]=head[a2],sz[a3]=sz[a2],comb[a3]=comb[a2],head[a2]=sz[a2]=comb[a2]=0;
23             else{
24                 if(sz[a2]<sz[a3]){
25                     int a4=head[a2],a6=head[a3]; 
26                     while(a4){
27                         int a5=next[a4];
28                         for(;a4<a6&&next[a6]>0;a6=next[a6]);
29                         if(a4<a6)next[a6]=a4,last[a4]=a6,next[a4]=0;
30                         else if(last[a6]==0)last[a4]=0,next[a4]=a6,last[a6]=a4,head[a3]=a4;
31                         else next[last[a6]]=a4,last[a4]=last[a6],next[a4]=a6,last[a6]=a4;
32                         sz[a3]++; a4=a5;
33                     }
34                     sz[a2]=head[a2]=0;
35                 }else{
36                     int a4=head[a3],a6=head[a2]; 
37                     while(a4){
38                         int a5=next[a4];
39                         for(;a4<a6&&next[a6]>0;a6=next[a6]);
40                         if(a4<a6)next[a6]=a4,last[a4]=a6,next[a4]=0;
41                         else if(last[a6]==0)last[a4]=0,next[a4]=a6,last[a6]=a4,head[a2]=a4;
42                         else next[last[a6]]=a4,last[a4]=last[a6],next[a4]=a6,last[a6]=a4;
43                         sz[a2]++; a4=a5;
44                     }
45                     head[a3]=head[a2],sz[a3]=sz[a2],head[a2]=sz[a2]=0;
46                 }
47                 ans-=comb[a2]; ans-=comb[a3]; comb[a2]=comb[a3]=0;
48                 for(int i=head[a3];i;i=next[i])if(i==head[a3]||i!=last[i]-1)comb[a3]++;
49                 ans+=comb[a3];
50             }
51         }
52     }
53     return 0;
54 }      

20160320

轉載于:https://www.cnblogs.com/YuanZiming/p/5656750.html