【luogu P1972 [SDOI2009]HH的项链】 题解

题目链接：https://www.luogu.org/problemnew/show/P1972
真是不懂为什么要卡莫队！

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2000100;
int a[maxn], n, m, ans[maxn], last[maxn];
struct Query{
	int l, r, p;
}q[maxn];
bool cmp(const Query &a, const Query &b)
{
    return a.r<b.r;
}
struct BIT{
	int data[maxn], num;
	void add(int pos, int val)
	{
		while(pos <= num)
		{
			data[pos] += val;
			pos += (pos&(-pos));
		}
		return;
	}
	int sum(int pos)
	{
		int sum = 0;
		while(pos)
		{
			sum += data[pos];
			pos -= (pos&(-pos));
		}
		return sum;
	}
	int query(int l, int r)
	{
		return sum(r) - sum(l-1);
	}
}bit;
int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	scanf("%d",&a[i]);
	bit.num = n;
	scanf("%d",&m);
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].p = i;
	}
	sort(q+1,q+1+m,cmp);
	int Q = 0;
	for(int i = 1; i <= m; i++)
	{
		while(Q < q[i].r)
		{
			Q+=1;
			if(last[a[Q]])
			{
				bit.add(last[a[Q]],-1);
				bit.add(Q,1);
				last[a[Q]] = Q;
			}
			else
			{
				bit.add(Q,1);
				last[a[Q]] = Q;
			}
		}
		ans[q[i].p] = bit.query(q[i].l,q[i].r);
	}
	for(int i = 1; i <= m; i++)
	printf("%d
",ans[i]);
	return 0;
}