BZOJ 2120 数颜色 - NekoMio's Blog

题目描述#

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

输入#

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出#

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

样例输入#

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

样例输出#

4
4
3
4

提示#

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。 2016.3.2新加数据两组by Nano_Ape

题解#

计算出 i 的前一个出现的位置
然后就和教主的魔法一样了
注意数组大小

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cmath>
5
int comp(int a, int b)
6
{
7
    return a > b;
8
}
9
using namespace std;
10
int pre[10005], front[1000005];
11
int in[10005];
12
int a[10005], b[10005];
13
int n, block;
14
void build(int x)
15
{
16
    for (int i = (x - 1) * block + 1; i <= min(x * block, n); i++)
17
    {
18
        pre[i] = b[i];
19
    }
20
    sort(pre + (x - 1) * block + 1, pre + min(x * block + 1, n + 1));
21
}
22
void rebuild(int k, int x)
23
{
24
    for (int i = 1; i <= n; i++)
25
        front[a[i]] = 0;
26
    a[k] = x;
27
    for (int i = 1; i <= n; i++)
28
    {
29
        int ls = b[i];
30
        b[i] = front[a[i]];
31
        if (ls != b[i])
32
            build(in[i]);
33
        front[a[i]] = i;
34
    }
35
}
36
int query(int c, int x)
37
{
38
    int l = (x - 1) * block + 1, r = min(n, x * block);
39
    int head = l;
40
    while (l <= r)
41
    {
42
        int m = (l + r) >> 1;
43
        if (pre[m] < c)
44
            l = m + 1;
45
        else
46
            r = m - 1;
47
    }
48
    return l - head;
49
}
50
int Query(int l, int r)
51
{
52
    int ans = 0;
53
    if (in[l] == in[r])
54
    {
55
        for (int i = l; i <= r; i++)
56
            if (b[i] < l)
57
                ans++;
58
    }
59
    else
60
    {
61
        for (int i = l; i <= min(block * in[l], n); i++)
62
            if (b[i] < l)
63
                ans++;
64
        for (int i = block * (in[r] - 1) + 1; i <= r; i++)
65
            if (b[i] < l)
66
                ans++;
67
    }
68
    for (int i = in [l] + 1; i < in[r]; i++)
69
        ans += query(l, i);
70
    return ans;
71
}
72
int main()
73
{
74
    //freopen("nt2011_color.in","r",stdin);
75
    //freopen("nt2011_color.out","w",stdout);
76
    //freopen("1.in", "r", stdin);
77
    int m;
78
    scanf("%d%d", &n, &m);
79
    block = sqrt(n);
80
    for (int i = 1; i <= n; i++)
81
    {
82
        scanf("%d", &a[i]);
83
        b[i] = front[a[i]];
84
        front[a[i]] = i;
85
        in[i] = (i - 1) / block + 1;
86
    }
87
    int tot = in[n];
88
    for (int i = 1; i <= tot; i++)
89
        build(i);
90
    char s[10];
91
    int l, r;
92
    while (m--)
93
    {
94
        scanf("%s", s);
95
        if (s[0] == 'Q')
96
        {
97
            scanf("%d%d", &l, &r);
98
            printf("%d\n", Query(l, r));
99
        }
100
        else
101
        {
102
            scanf("%d%d", &l, &r);
103
            rebuild(l, r);
104
        }
105
    }
106
}