Luogu P1972 [SDOI2009]HH的项链

树状数组维护。

区间差分后的前缀和就是原区间。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
struct node
{
	int l, r, id;
};
node que[maxn];
int cmp(node a, node b)
{
	return a.r < b.r;
}
int tree[maxn], num[maxn], use[maxn], ans[maxn], n, m;
int lowbit(int x)
{
	return x & (-x);
}
void update(int pos, int x)
{
	while(pos <= n)
	{
		tree[pos] += x;
		pos += lowbit(pos);
	}
	return;
}
int query(int pos)
{
	int ret = 0;
	while(pos)
	{
		ret += tree[pos];
		pos -= lowbit(pos);
	}
	return ret;
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &num[i]);
	}
	scanf("%d", &m);
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d", &que[i].l, &que[i].r);
		que[i].id = i;
	}
	sort(que + 1, que + m + 1, cmp);
	int last = 1;
	for(int i = 1; i <= m; i++)
	{
		for(int j = last; j <= que[i].r; j++)
		{
			if(use[num[j]])
			{
				update(use[num[j]], -1);
			}
			update(j, 1);
			use[num[j]] = j;
		}
		last = que[i].r + 1;
		ans[que[i].id] = query(que[i].r) - query(que[i].l - 1);
	}
	for(int i = 1; i <= m; i++)
	{
		printf("%d\n", ans[i]);
	}
	return 0;
}