[HNOI2009]梦幻布丁（链表+启发式合并）

洛谷传送门

开始一个O(n^2)思路，每次每句要改变颜色的点，改变完颜色后重新计算颜色的段数，显然拉闸。

然后呢。。然后就不会了。

看了别人博客，才知道有个叫做启发式合并的东西，就是把小的合并到大的上面，时间复杂度就将为了log级别，额，为啥呢？

反正这样就更快了。

然后对于此题

我们先求出原序列的答案

每一种颜色搞一条链把该色结点串起来，记录下链条尾结点

把一种颜色的染成另一种，很简单把它合并过去，然后处理下对于答案的影响

但是。。。

比如把1染成2，但是s[1]>s[2]，这时我们应该将2合并到1的链后面，但是会遇到一个麻烦的问题，就是这个链头是接1下的，也就是说以后找颜色2，发现没有颜色2只有颜色1。。。

于是我们应该开一个数组f，表示我们寻找一种颜色时，实际应该找哪个颜色下的链，遇到上面那种情况要交换f[1]和f[2]

 #include <iostream>

 #include <cstdio>

 #define maxn 100005

 using namespace std;

 int n, m, maxx, ans;

 int a[maxn], next[maxn], head[maxn * ], tail[maxn * ], cnt[maxn * ], f[maxn * ];

 int main()

 {

     int i, j, x, y, opt;

     scanf("%d %d", &n, &m);

     for(i = ; i <= n; i++)

     {

         scanf("%d", &a[i]);

         f[a[i]] = a[i];

         if(a[i] != a[i - ]) ans++;

         if(!tail[a[i]]) head[a[i]] = i;

         next[i] = tail[a[i]];

         tail[a[i]] = i;

         cnt[a[i]]++;

     }

     for(i = ; i <= m; i++)

     {

         scanf("%d", &opt);

         if(opt == )

         {

             scanf("%d %d", &x, &y);

             if(f[x] == f[y]) continue;

             if(cnt[f[x]] > cnt[f[y]]) swap(f[x], f[y]);//表头互换

             x = f[x], y = f[y];

             if(!cnt[x]) continue;

             for(j = tail[x]; j; j = next[j])

             {

                 if(a[j - ] == y) ans--;

                 if(a[j + ] == y) ans--;

             }

             for(j = tail[x]; j; j = next[j]) a[j] = y;

             next[head[x]] = tail[y];//把 x 合并到 y 上

             tail[y] = tail[x];

             cnt[y] += cnt[x];

             head[x] = tail[x] = cnt[x] = ;

         }

         else printf("%d\n", ans);

     }

     return ;

 }

把 x 插到 y 的后面，所以得写成

next[head[x]] = tail[y];

tail[y] = tail[x];

也可以把 x 插到 y 的前面，写成

next[head[y]] = tail[x];

head[y] = head[x]

巴特西

[HNOI2009]梦幻布丁（链表+启发式合并）

最新文章

热门文章