(luogu1972)HH的项链

发表于 | 分类于 ， ，

原题链接

思路:

原本是一个莫队的模板题, 数据加强后1e6的数据范围显然莫队是过不去了.

将询问按r排序, 然后考虑从左往右扫描所有询问.

从左往右扫描时, 对于某个数, 只需要考虑其最右出现的位置.

可以使用一个树状数组维护位置信息. 若当前位置的数是最右位置的数则置为1, 否则置为0. 这样sum(r) - sum(l-1)便是询问的答案.

代码:

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
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int Mn(1000500);
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) {
    qrd(x); qrd(xs...);
}

int n;
int arr[Mn], c[Mn], aps[Mn];    //原数组, 树状数组, 最后出现位置
struct qrd {
    int l, r, id;
    bool operator < (const qrd& rhs) const {
        return r<rhs.r;
    }
}aq[Mn];    //所有询问
int ans[Mn];    //答案

inline int lb(const int& x) {   //lowbit
    return x&-x;
}
void mdf(int p,int mx) {    //修改
    for(; p<=n; p+=lb(p)) {
        c[p] += mx;
    }
}
int sum(int p) {    //查询
    int ret(0);
    for(; p; p-=lb(p)) {
        ret += c[p];
    }
    return ret;
}

int main() {
    qrd(n);
    for(int i(1);i<=n;++i) {
        qrd(arr[i]);
    }
    int m; qrd(m);
    for(int i(1);i<=m;++i) {
        qrd(aq[i].l, aq[i].r);
        aq[i].id = i;
    }
    sort(aq+1,aq+m+1);
    for(int i(1), p(1); i<=n; ++i) {
        if(aps[arr[i]]) {   //若之前出现过将之前出现位置置0
            mdf(aps[arr[i]],-1);
        }
        aps[arr[i]] = i;
        mdf(i,1);
        while(p<=m && aq[p].r==i) { //解决询问
            ans[aq[p].id] = sum(aq[p].r) - sum(aq[p].l-1);
            ++p;
        }
    }
    for(int i(1);i<=m;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}