BZOJ1483 [HNOI2009] 梦幻布丁

BZOJ

洛谷

链表+启发式合并

懒得写链表

std::set代替链表

首先算出初始状态答案

然后对于每个修改操作,启发式合并两种颜色。

启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。

简单来说就是弱肉强食。

而且启发式合并的时间复杂度可以证明是O(logn)的

对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。

对于查询操作,由于每次修改同时都计算出答案,直接输出即可。


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
#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>


const int N = 1000000 + 10;


int a[N], f[N];
std::set <int> c[N];


int read(void);


int main(void)
{
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        f[a[i]] = a[i];
        c[a[i]].insert(i);
        if (a[i] != a[i - 1])
            ++ans;
    }
    while (m--)
    {
        int op = read();
        if (op == 1)
        {
            int x = read(), y = read();
            if (x != y)
            {
                if (c[f[x]].size() > c[f[y]].size())
                    std::swap(f[x], f[y]);
                x = f[x];
                y = f[y];
                for (std::set <int> ::iterator i = c[x].begin(); i != c[x].end(); ++i)
                    ans -= (y == a[*i - 1]) + (y == a[*i + 1]);
                for (std::set <int> ::iterator i = c[x].begin(); i != c[x].end(); ++i)
                {
                    a[*i] = y;
                    c[y].insert(*i);
                }
                c[x].clear();
            }
        }
        else
            printf("%d\n", ans);
    }
    return 0;
}


inline int read(void)
{
    char x;
    while (!isdigit(x = getchar()))
        ;
    int num = x - '0';
    while (isdigit(x = getchar()))
        (num *= 10) += x - '0';
    return num;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注