洛谷传送门
开始一个O(n^2)思路，每次每句要改变颜色的点，改变完颜色后重新计算颜色的段数，显然拉闸。
然后呢。。然后就不会了。
看了别人博客，才知道有个叫做启发式合并的东西，就是把小的合并到大的上面，时间复杂度就将为了log级别，额，为啥呢？
反正这样就更快了。
然后对于此题
我们先求出原序列的答案
每一种颜色搞一条链把该色结点串起来，记录下链条尾结点
把一种颜色的染成另一种，很简单把它合并过去，然后处理下对于答案的影响
但是。。。
比如把1染成2，但是s[1]>s[2]，这时我们应该将2合并到1的链后面，但是会遇到一个麻烦的问题，就是这个链头是接1下的，也就是说以后找颜色2，发现没有颜色2只有颜色1。。。
于是我们应该开一个数组f，表示我们寻找一种颜色时，实际应该找哪个颜色下的链，遇到上面那种情况要交换f[1]和f[2]
1 #include <iostream> 2 #include <cstdio> 3 #define maxn 100005 4 5 using namespace std; 6 7 int n, m, maxx, ans; 8 int a[maxn], next[maxn], head[maxn * 10], tail[maxn * 10], cnt[maxn * 10], f[maxn * 10]; 9 10 int main() 11 24 for(i = 1; i <= m; i++) 25 39 for(j = tail[x]; j; j = next[j]) a[j] = y; 40 next[head[x]] = tail[y];//把 x 合并到 y 上 41 tail[y] = tail[x]; 42 cnt[y] += cnt[x]; 43 head[x] = tail[x] = cnt[x] = 0; 44 } 45 else printf("%d\n", ans); 46 } 47 return 0; 48 }View Code
把 x 插到 y 的后面，所以得写成
next[head[x]] = tail[y]; tail[y] = tail[x];也可以把 x 插到 y 的前面，写成
next[head[y]] = tail[x]; head[y] = head[x]上一篇：双连通分量
下一篇：【模板】二分图最大权完美匹配KM算法
启发式合并 模拟
