HDU 5997 Rausen Loves Cakes

链接

传送门

题意

给出一个颜色的序列,每次有两种操作:

  • $1 \space x \space y$:将所有的颜色$x$变为颜色$y$;
  • $2 \space l \space r$:查询$[l, r]$之间有多少个连续的颜色段。

对于每次查询操作,输出查询的结果。

思路

用bit维护当前点是不是新的颜色的开始,然后可以用前缀和算出区间内颜色的段数。对于修改进行启发式合并,储存每种颜色的位置,对于合并,将少的颜色合并到多的颜色上。

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 100010;
const int maxm = 1000010;
int n, bit[maxn];
int a[maxn], p[maxm];
bool ok[maxn];
vector<int> g[maxm];
inline int lowbit(int x) {
return x & -x;
}
int Sum(int x) {
int res = 0;
while (x > 0) {
res += bit[x];
x -= lowbit(x);
}
return res;
}
void Add(int x, int d) {
while (x <= n) {
bit[x] += d;
x += lowbit(x);
}
}
void proc(int p) {
if (ok[p] && a[p] == a[p - 1]) {
ok[p] = false;
Add(p, -1);
}
}
void proc(int &x, int &y) {
for (int &v: g[x]) {
g[y].push_back(v);
a[v] = y;
proc(v);
proc(v + 1);
}
g[x].clear();
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int m, op, x, y;
scanf("%d%d", &n, &m);
memset(ok, 0, sizeof ok);
memset(bit, 0, sizeof bit);
for (int i = 1; i < maxm; ++i) {
p[i] = i;
g[i].clear();
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
g[a[i]].push_back(i);
if (a[i] != a[i - 1]) {
Add(i, 1);
ok[i] = true;
}
}
while (m--) {
scanf("%d%d%d", &op, &x, &y);
if (op == 1 && p[x] != p[y]) {
if (g[p[x]].size() < g[p[y]].size()) {
proc(p[x], p[y]);
} else {
proc(p[y], p[x]);
swap(p[x], p[y]);
}
} else if (op == 2) {
int ans = Sum(y) - Sum(x - 1);
if (!ok[x]) {
++ans;
}
printf("%d\n", ans);
}
}
}
return 0;
}

支付宝扫码领红包