$n$ 个布丁摆成一行，每个布丁最开始都有一个颜色 $c_i$ ，进行 $m$ 次操作。
操作格式：
链接
Luogu P3201
题解
这题非常有趣。开始想倒是像以前做过的 [SDOI2011]染色 ，不过仔细想想这个东西很难用线段树进行维护。
由于这道题放在平衡树的专题里，我们思考一下这个东西能不能用平衡树维护。
重点需要解决的问题是如何合并两种颜色（因为颜色段肯定是单调递减的）。我们可以想到使用平衡树的启发式合并。合并的时候更新答案的情况只有当前这个位置的 $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;
}
|
