P1972 HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 n，表示项链长度。
第二行 n 个正整数 ai，表示项链中第 i 个贝壳的种类。

第三行一个整数 m，表示 HH 询问的个数。
接下来 m 行，每行两个整数 l,r，表示询问的区间。

1≤n,m,ai≤106，1≤l≤r≤n。

输出格式

输出 m 行，每行一个整数，依次表示询问对应的答案。

Solution

树状数组/线段树/可持久化线段树

和 P2184 贪婪大陆有点像

对于区间内相同的数字，只保留最后一次出现的数字。按照右端点排序。

向右滑动计算，以每一个区间的右端点为界限。

每次移到下一个端点后，如果已经存在，则将存在的那个点删除，再加上新点下标，滑动完该区间后，计算在该区间的区间和即为种类个数。

#define lowbit(x) x&(-x)
const int N = 1000010;
int n, a[N], tr[N], last[N], ans[N];
array<int, 3> q[N];
void add(int x, int k) {
    while (x <= n)tr[x] += k, x += lowbit(x);
}
int query(int x) {
    int ans = 0;
    while (x)ans += tr[x], x -= lowbit(x);
    return ans;
}
void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int m;cin >> m;
    for (int i = 1;i <= m;i++) {
        int l, r; cin >> l >> r;
        q[i] = {l,r,i};
    }
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        return x[1] < y[1];
        });
    int lp = 1;//当前滑动的位置
    for (int i = 1;i <= m;i++) {//对于每一个区间
        for (int j = lp;j <= q[i][1];j++) {//从当前位置继续出发
            if (last[a[j]])add(last[a[j]], -1);
            add(j, 1);
            last[a[j]] = j;//将这个数字最后一次出现的位置更新
        }
        lp = q[i][1] + 1;
        ans[q[i][2]] = query(q[i][1]) - query(q[i][0] - 1);
    }
    for (int i = 1;i <= m;i++)cout << ans[i] << '\n';
}