题目链接：HH的项链
这道题做法很多，看到有用线段树，主席树和莫队做的，但我不太会用树状数组，所以讲解一下树状数组的解法。
题干告诉我们要求区间内的贝壳的种类数，那么用树状数组怎么维护呢？我们通过一个简单的例子来理解一下。对于一个序列：1 4 3 2 4 2，我们要去求这个序列里的贝壳的个数，我们就要考虑去重，将这个序列变为1 4 3 2 0 0，这样就代表了\(1\sim6\)里的贝壳的种类数。
但是我们会发现一个问题，就是这样处理的话我们要想求\(3\sim6\)，结果就会是2，但实际上的答案应该是3，那么我们就可以把某一区间内比较靠后的贝壳，作为这一区间内这种贝壳出现的唯一次数，然后记录一下上一个同种贝壳出现的位置，更新传递一下即可。具体做法就是将询问区间的操作离线，按右端点的大小进行排序，然后一一枚举贝壳的数量即可。
代码实现：
点击查看代码
#define lowbit(x) x & (-x)
using namespace std;
const int M = 1e6 + 10;
struct node {
int l, r, id;
friend bool operator<(node x1,node x2) {
if (x1.r == x2.r) return x1.l < x2.l;
return x1.r < x2.r;
}
} plan[M];
int n, m, k=1;
int a[M], p[M], ans[M], c[M];
void add(int x, int val) {
for (int i = x; i <= n; i += lowbit(i))
c[i] += val;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += c[i];
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> plan[i].l >> plan[i].r;
plan[i].id = i;
}
sort(plan + 1, plan + 1 + m);
for (int i = 1; i <= plan[m].r; i++) {
if (!p[a[i]]) {
p[a[i]] = i;
add(i, 1);
} else {
add(p[a[i]], -1);
p[a[i]] = i;
add(p[a[i]], 1);
}
while (i == plan[k].r) {
ans[plan[k].id] = query(plan[k].r) - query(plan[k].l-1);
k++;
}
}
for (int i = 1; i <= m; i++)
cout << ans[i] << '\n';
return 0;
}