The coding life...

0%

维护区间不同颜色

发表于 更新于 分类于

其实就是这道题：HH的项链

离线转化成一个单点修改区间查询的问题。这样就可以用线段树或者树状数组做了。//用树状数组简单多了。。

先把所有询问以右端点排序，然后慢慢向后解决。

记录一下每个颜色最后出现在的地方，然后如果这个地方又出现了那种颜色的话，就把之前那个地方的颜色抹掉，然后在这里记上这种颜色，在更新表示每个颜色最后出现的数组。

code:

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
91
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define INF 0x3f3f3f3f
#define NO 600100
#define MO 1000005
typedef long long ll;
//by Oliver
using namespace std;
ll read()
{
    char ch = ' ', last;
    ll ans = 0;
    while (ch < '0' || ch > '9')
        last = ch, ch = getchar();
    while (ch >= '0' && ch <= '9')
        ans = ans * 10 + int(ch - '0'), ch = getchar();
    if (last == '-')
        return -ans;
    return ans;
}
//head

int n, a[NO], m, d[NO], last[MO];
struct node
{
    int L, R, pos, ans;
}asks[NO];
//variable

int lowbit(int x)
{
    return x & -x;
}
void add(int val, int pos)
{
    for(int i = pos; i <= n; i += lowbit(i))
        d[i] += val;
}
int ask(int pos)
{
    int ans = 0;
    for(int i = pos; i; i -= lowbit(i))
        ans += d[i];
    return ans;
}
bool cmp1(node i, node j)
{
    return i.R < j.R;
}
bool cmp2(node i, node j)
{
    return i.pos < j.pos;
}
void init()
{
    n = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
    m = read();
    for(int i = 1; i <=m; i++)
        asks[i].L = read(), asks[i].R = read(), asks[i].pos = i;
    sort(asks + 1, asks + m + 1, cmp1);
}
//functions

int main()
{
    init();
    memset(last, 0, sizeof(last));
    int now = 1;
    for(int i = 1; i <= m; i++)
    {
        for(; now <= asks[i].R; now++)
        {
            if(last[a[now]])
                add(-1, last[a[now]]);
            add(1, now), last[a[now]] = now;
        }
        asks[i].ans = ask(asks[i].R) - ask(asks[i].L - 1);
    }
    sort(asks + 1, asks + m + 1, cmp2);
    for(int i = 1; i <= m; i++)
        cout << asks[i].ans << endl;
    return 0;
}
//main

其实这题应该还可以用一些其他方法做(莫队之类的)。但是其实是卡不过去的，（最好成绩也只有90pt..）

然后这种思路还可以去维护不止数量不少于$2$个的颜色数量等等。//一道贪心模拟赛上的题。

此外好像也可以用主席树做。学了更。