DDOSvoid's Blog

SP3267 DQUERY - D-query

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/SP3267

Solution

我们令 $pre[i]$ 表示 $a[i]$ 上次出现的位置，那么对于区间 $[l,r]$，我们只需要统计区间中小于 $l-1$ 的 $pre[i]$ 的个数即可

注意到区间中相同的数只会被统计一次，可以用主席树实现

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
#include <iostream>
#include <cstdio>
#define maxn 30010
using namespace std;

int n, m, a[maxn];

int pre[maxn], b[maxn];

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
    int v, ch[2];
} T[maxn * 20]; int top, rt[maxn];
void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; T[i].v += v;
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v);
}

int query(int i, int j, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[j].v - T[i].v;
    int m = l + r >> 1;
    return query(lc, Lc, l, m, L, R) + query(rc, Rc, m + 1, r, L, R);
}


int main() {
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; pre[i] = b[a[i]];
        b[a[i]] = i; 
    }
    for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 0, n - 1, pre[i], 1);
    cin >> m; 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        printf("%d\n", query(rt[x - 1], rt[y], 0, n - 1, 0, x - 1));
    }
    return 0;
}

另外还有一种方法，本质上就是枚举右端点用线段树维护左端点的过程，然后我们强制在线，把这东西搬到主席树上即可

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 300010
#define maxm 1000010
using namespace std;

int n, m, a[maxn];

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
    int v, ch[2];
} T[maxn * 40]; int top, rt[maxn];
void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; T[i].v += v;
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v);
}

int query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1;
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R); 
}

int p[maxm];
int main() {
    cin >> n; 
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    cin >> m;
    for (int i = 1; i <= n; ++i) {
        rt[i] = rt[i - 1];
        if (p[a[i]]) update(rt[i], rt[i - 1], 1, n, p[a[i]], -1);
        update(rt[i], rt[i], 1, n, i, 1); p[a[i]] = i; 
    }
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", query(rt[y], 1, n, x, y));
    }          
    return 0;
}