Description

题目链接

题目大意:每次询问 $[l, r]$ 内不同的数的个数。$1 \le n, m \le 10^6$。

Solution

由于每个数的在一个区间内的出现位置对答案没有影响,因此可以离线后前缀和解决问题。

将询问按右端点排序,每次扩展当前区间,同时每次让 $a_i$ 的贡献由当前区间内最右边的 $a_i$ 产生。

询问的答案用前缀和处理即可。

时间复杂度 $O(m \log n)$。

之前可以用莫队过,现在不行了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Query {
    int l, r, id;
    friend bool operator < (const Query &a, const Query &b) {
        return a.r < b.r;
    }
} b[1000010];

int a[1000010], t[1000010], ans[1000010], pos[1000010];
int n, m, now = 1;

void modify(int x, int d) {
    for (; x <= n; x += x & -x)    t[x] += d;
    return ;
}

int query(int x) {
    int s = 0;
    for (; x; x -= x & -x)    s += t[x];
    return s;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i)    read(a[i]);
    read(m);
    for (int i = 1; i <= m; ++i)    read(b[i].l), read(b[i].r), b[i].id = i;
    std::sort(b + 1, b + m + 1);
    for (int i = 1; i <= m; ++i) {
        for (int j = now; j <= b[i].r; ++j) {
            if (pos[a[j]])    modify(pos[a[j]], -1);
            modify(j, 1);
            pos[a[j]] = j;
        }
        now = b[i].r + 1;
        ans[b[i].id] = query(b[i].r) - query(b[i].l - 1);
    }
    for (int i = 1; i <= m; ++i)    printf("%d\n", ans[i]);
    return 0;
}
Last modification:November 16th, 2021 at 08:41 pm