统计区间内不同数的个数

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟
If you want something you've never had, then you've got to do something you've never done.

模板题：题目传送门

解法 1：离线 + 树状数组

思路：

  • 先离线下，对询问的r排序，以元素的下标作树状数组维护以r为右边界的区间不同元素的数量，遍历时如果当前元素没有出现，那么存在他的地址，并在树状数组对应下标+1，如果这个元素
  • 之前已经出现过了，那么取消之前标记的点也就是将这个元素上一次出现的下标在树状数组中-1，变成0，然后再储存下当前元素最迟出现的下标，也就是当前点。
  • 最后区间[l,r]之间不同的数量也就是sumR - sumL

时间复杂度：

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
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E6 + 10;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x; i < n; i += i & -i) {
            a[i] = a[i] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    Fenwick<int> fen(n + 1);

    std::vector<int> a(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i + 1];
    }
    
    int m;
    std::cin >> m;

    std::vector<std::array<int, 3>> q(m + 1);
    for (int i = 1; i <= m; i++) {
        std::cin >> q[i][0] >> q[i][1];
        q[i][2] = i;
    }

    std::sort(q.begin() + 1, q.end(), [&](auto i, auto j) {
        return i[1] < j[1];
    });

    int l = 1;
    std::vector<int> vis(N), ans(N);
    for (int i = 1; i <= m; i++) {
        for (int j = l; j <= q[i][1]; j++) {
            if (vis[a[j]]) {
                fen.add(vis[a[j]], -1);
            }
            fen.add(j, 1);
            vis[a[j]] = j;
        }
        l = q[i][1] + 1;
        ans[q[i][2]] = fen.rangeSum(q[i][0] - 1, q[i][1]);
    }
    for (int i = 1; i <= m; i++) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}

解法 2：莫队

思路：

  • 这道题感觉就是直接莫队莽上就完事了，没有什么需要处理的，就维护下每个元素在当前区间出现的次数就好了

时间复杂度：

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
#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int  maxn = 1e6 + 10;
int a[maxn], n, num[maxn], m, ans, block, vis[maxn];
 
struct node {
    int l, r, id;
    bool operator<(const node &b) const {
        if (l / block == b.l / block) return r < b.r;
        return l / block < b.l / block;
    }
}q[maxn];
 
void add(int x) {
    vis[a[x]]++;
    if (vis[a[x]] == 1) ans++;
}
void del(int x) {
    vis[a[x]]--;
    if (vis[a[x]] == 0) ans--;
}
int main() {
    scanf("%d", &n);
    block=sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    int l = 1,r = 0;
    for (int i = 1; i <= m; i++) {
        while (l < q[i].l) {
            del(l);
            l++;
        }
        while (l > q[i].l) {
            l--;
            add(l);
        }
        while (r < q[i].r) {
            r++;
            add(r);
        }
        while (r > q[i].r) {
            del(r);
            r--;
        }
        num[q[i].id] = ans;
    }
    for (int i = 1; i <= m; i++) {
        printf("%d\n", num[i]);
    }
}

解法 3：主席树

思路：

  • 我们将元素在序列中的地址建成主席树，如果这个元素没有出现过，那么就在这个位置上+1，如果这个元素出现过那就将这个元素上一次出现的位置-1，在当前位置+1；每棵线段树维护的都是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
74
75
#include <bits/stdc++.h> 

using i64 = long long;

constexpr int N = 100010;
struct node {
    int l, r, sum;
}tr[N * 40];
int root[N], vis[N], tot, res;

void add(int l, int r, int pre, int &now, int p, int c) {
    tr[++tot] = tr[pre];
    now = tot;
    tr[now].sum += c;
    if (l == r) {
        return ;
    }
    int mid = l + r >> 1;

    if (p <= mid) {
        add(l, mid, tr[pre].l, tr[now].l, p, c);
    } else {
        add(mid + 1, r, tr[pre].r, tr[now].r, p, c);
    }
}

void query(int k, int l, int r, int p) {
    if (p == l) {
        res += tr[k].sum;
        return ;
    }
    int mid = l + r >> 1;
    if (p <= mid) {
        res += tr[tr[k].r].sum;
        query(tr[k].l, l, mid, p);
    } else {
        query(tr[k].r, mid + 1, r, p);
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
        
    int n;
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        int x;  
        std::cin >> x;

        int t = 0;
        if (!vis[x]) {
            add(1, n, root[i - 1], root[i], i, 1);
        } else {
            add(1, n, root[i - 1], t, vis[x], -1);
            add(1, n, t, root[i], i, 1);
        }
        vis[x] = i;
    }
    
    int q;
    std::cin >> q;
    
    while (q--) {
        int l, r;
        std::cin >> l >> r;

        res = 0;
        query(root[r], 1, n, l);
        std::cout << res + 1 << "\n";
    }

    return 0;
}

参考