Description：

给你一个数列，多次询问区间 $[l,r]$ 中有多少个数出现了多于一次。

$1\le n \le 2\times10^6$

Solution：

先把所有询问离线下来按右端点排序，然后两个指针一个扫数列一个扫询问，遇到一个小于右端点的数就把他的上一次出现的位置加入树状数组，把他上上次出现的位置从树状数组中删除，也就是说树状数组中时刻保存的都是每个数倒数第二次出现的位置，那么只要查询这些位置中有多少个在 $[l,r]$ 内，就有多少个出现了超过两次。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,w,m;

#define MAXN 2000010

int a[MAXN],pre[MAXN],last[MAXN];

struct opt

{

	int l,r,ans,id;

	opt(){ans = 0;}

}s[MAXN];

bool cmp_r(opt a,opt b){return a.r < b.r;}

bool cmp_id(opt a,opt b){return a.id < b.id;}

inline int lowbit(int x){return x & (-x);}

int c[MAXN];

inline void add(int p,int x)

{

	for(register int i = p;i <= n;i += lowbit(i))c[i] += x;

	return;

}

inline int query(int p)

{

	register int res = 0;

	for(register int i = p;i >= 1;i -= lowbit(i))res += c[i];

	return res;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	scanf("%d%d%d",&n,&w,&m);

	for(register int i = 1;i <= n;++i)

	{

		a[i] = read();

		pre[i] = last[a[i]];

		last[a[i]] = i;

	}

	for(register int i = 1;i <= m;++i)

	{

		s[i].l = read();s[i].r = read();

		s[i].id = i;

	}

	sort(s + 1,s + 1 + m,cmp_r);

	for(register int i = 1,j = 1;i <= m;++i)

	{

		for(;j <= s[i].r;++j)

		{

			if(pre[pre[j]] != 0)add(pre[pre[j]],-1);

			if(pre[j] != 0)add(pre[j],1);

		}

		s[i].ans = query(s[i].r - 1) - query(s[i].l - 1);

	}

	sort(s + 1,s + 1 + m,cmp_id);

	for(register int i = 1;i <= m;++i)

	{

		printf("%d\n",s[i].ans);

	}

	return 0;

}