「HNOI2009」梦幻布丁-set-启发式合并

$n$个布丁摆成一行,每个布丁最开始都有一个颜色$c_i$,进行$m$次操作。

操作格式:

  • 1 c d表示将所有的$c$颜色替换为$d$

  • 2代表查询当前布丁序列一共有多少段颜色。例如颜色分别为$1,2,2,1$的四个布丁一共有3段颜色。

链接

Luogu P3201

题解

这题非常有趣。开始想倒是像以前做过的 ,不过仔细想想这个东西很难用线段树进行维护。

由于这道题放在平衡树的专题里,我们思考一下这个东西能不能用平衡树维护。

重点需要解决的问题是如何合并两种颜色(因为颜色段肯定是单调递减的)。我们可以想到使用平衡树的启发式合并。合并的时候更新答案的情况只有当前这个位置的$pos-1$或者$pos+1$的位置有相同颜色的位置的时候,我们都需要对答案减去1。

启发式合并可以让复杂度降低一个$log$,最后时间复杂度就是$O(n \log^2{n})$。最坏情况就是每次合并的区间大小都相等的情况,合并起来的次数$O(n \log {n})$。

有$O(n \log{n})$的奇怪做法,具体我也就不会了。

具体实现上,可以维护一个数组记录当前某个数对应的set位置,就可以减去一些不必要消耗。

代码

点击切换显示状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
#include <set>
#include <cctype>
using namespace std;

const int MAXN = 1100000;

namespace fast_io {
//...
}using namespace fast_io;

int n,m,ans = 0;
int num[MAXN],re[MAXN];
set<int> S[MAXN];

void update(int last,int now){
for(set<int>::iterator it = S[last].begin();it!=S[last].end();it++){
if(num[(*it)-1] == (now))
ans--;
if(num[(*it)+1] == (now))
ans--;
S[now].insert(*it);
}
for(set<int>::iterator it = S[last].begin();it!=S[last].end();it++)
num[*it] = now;
S[last].clear();
}

void init(){
read(n),read(m);
for(int i = 1;i<=n;i++){
read(num[i]);
if(num[i]!=num[i-1]) ans++;
S[num[i]].insert(i);
re[num[i]] = num[i];
}
}

void solve(){
int op,a,b;
for(int i = 1;i<=m;i++){
read(op);
if(op == 1){
read(a),read(b);
if(a == b) continue;//很重要!
if(S[re[a]].size() > S[re[b]].size()) swap(re[a],re[b]);
update(re[a],re[b]);
}
else if(op == 2){
print(ans),print('\n');
}
}
}

int main(){
init();
solve();
flush();
return 0;
}