HDU 5997 rausen loves cakes

发表于 分类于 Disqus：

链接

传送门

题意

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

  • \(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;
}
相关文章