【数据结构专题班树状数组、线段树练习题】B [SDOI2009] HH的项链 题解

考点

树状数组
离线查询

分析

先把要查询的区间离线下来，对它们按照右边界从小到大排序，保证只需要从左至右将数组扫描一次。一边利用树状数组即时更新维护不同的元素个数，一边进行查询并保存答案，这个过程是动态的，便于我们只记录最近出现的元素的位置。即从右边界往左看，最右边已经有的数，左边再出现就可忽略不计了。这就是离线查询的原因。

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn], n;
struct Node {
    int L, R, id;
    bool friend operator < (const Node &A, const Node &B) {
        return A.R < B.R;
    }
}ques[maxn];
int ans[maxn], last[maxn];
class Tree_array {
public:
    int tree[maxn];
    inline int lowbit(int x) {
        return x&(-x);
    }
    void add(int pos, int val) {
        while (pos <= n) {
            tree[pos] += val;
            pos += lowbit(pos);
        }
    }
    int query(int pos) {
        int sum = 0;
        while (pos >= 1) {
            sum += tree[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
};
int main()
{
    Tree_array tra;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ques[i].L >> ques[i].R;
        ques[i].id = i;
    }
    sort(ques + 1, ques + 1 + m);
    int pos = 1;
    memset(last, 0, sizeof(last));
    for (int i = 1; i <= m; i++) {
        for (; pos <= ques[i].R; pos++) {
            if (last[a[pos]])tra.add(last[a[pos]], -1);
            tra.add(pos, 1);
            last[a[pos]] = pos;
        }
        ans[ques[i].id] = tra.query(ques[i].R) - tra.query(ques[i].L - 1);
    }
    for (int i = 1; i <= m; i++)cout << ans[i] << endl;
    return 0;
}