题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2743

题目分类：离线，小数据结构

题意：

给出一个长度为n的序列，每次询问一个区间，问这个区间内有多少个数出现了超过一次。

题解：

离线处理。

考虑对于一个区间，一个元素对他有价值，当且仅当他的下一个相同的在这个区间内且他的上一个相同的不在区间内。

考虑将所有区间按照左端点排序，按顺序扫描所有的区间。

按照程序中展示的方案进行操作。

每次删除一个点，把他下一个相同元素的对应位置减一，下下个相同元素对应位置加一。

程序：

#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
inline int lowbit(int x)
{
	return (x&(-x));
}
struct node
{
	int a[1200000];
	inline void edit(int x,int v)
	{
		if(x==0)return;
		while (x<=1000000)
		{
			a[x]+=v;
			x+=lowbit(x);
		}
	}
	inline int query(int x)
	{
		int ss=0;
		while (x>0)
		{
			ss+=a[x];
			x-=lowbit(x);
		}return ss;
	}
}sgt;
int n,c,m;
int a[1200000];
int next[1200000];
pair<pair<int,int>,int>q[1200000];
int hash[1200000],ans[1200000];
int main()
{
	scanf("%d %d %d",&n,&c,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for (int i=n;i>=1;i--)
	{
		next[i]=hash[a[i]];
		hash[a[i]]=i;
	}
	for (int i=1;i<=c;i++)
	{
		sgt.edit(next[hash[i]],1);
	}
	for (int i=1;i<=m;i++)
	{
		scanf("%d %d",&q[i].first.first,&q[i].first.second);
		q[i].second=i;
	}
	int le=1;
	sort(q+1,q+m+1);
	for (int i=1;i<=m;i++)
	{
		while (le<q[i].first.first)
		{
			sgt.edit(next[le],-1);
			sgt.edit(next[next[le]],1);
			le++;
		}
		ans[q[i].second]=sgt.query(q[i].first.second)-sgt.query(q[i].first.first-1);
	}
	for (int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}