记录编号	15934	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	2.080 s
提交时间	2010-04-13 11:19:11	内存使用	10.61 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

using namespace  std;

const int maxn=50000+1;
const int maxm=200000+1;

int n,m;
bool y[1000001];
struct sl
{
	int v,id;
	sl *next;
}a[maxn],*V[1000001];

struct question
{
	int l,r,id,ans;
}q[maxm];

struct node
{
	int a,b,num;
	node *l,*r;
}P[2*maxn],*root=NULL;
int pn;
void makespe(node *&tk,int a,int b)
{
	int md=(a+b)/2;
	tk=&P[++pn];
	tk->a = a;  tk->b = b;  tk->num = 0;
	if (a!=b)
	{
		makespe(tk->l,a,md);
		makespe(tk->r,md+1,b);
	}
}

void insert(node *&tk,int i)
{
	if (tk && tk->a<=i && i<=tk->b) 
	{
		tk->num++;
		insert(tk->l,i);
		insert(tk->r,i);
	}
}

void del(node *&tk,int i)
{
	if (tk && tk->a<=i && i<=tk->b) 
	{
		tk->num--;
		del(tk->l,i);
		del(tk->r,i);
	}
}

int check(node *&tk,int a,int b)
{
	int now=0;
	if (tk)
	{
		if (tk->a>=a && b>=tk->b)
			now+=tk->num;
		else if (b<tk->a || a>tk->b) return 0;
		else
		{
			now += check(tk->l,a,b);
			now += check(tk->r,a,b);
		}
	}
	return now;
}

void init()
{
	scanf("%d",&n);
	makespe(root,1,n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].v);
		a[i].id=i;
		if (!y[a[i].v]) 
		{	
			y[a[i].v]=true;
			insert(root,i);
		}
	}
	for (int i=n;i>=1;i--)
	{
		a[i].next=V[a[i].v];
		V[a[i].v]=&a[i];
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		if (q[i].r<q[i].l) swap(q[i].r,q[i].l);
		q[i].id=i;
	}
}

int cmp(const void *a,const void *b)
{
	if (((question *)a)->l > ((question *)b)->l) return 1;
	else if (((question *)a)->l < ((question *)b)->l) return -1;
		else return ((question *)a)->r - ((question *)b)->r;
}

int cmp1(const void *a,const void *b)
{return ((question *)a)->id - ((question *)b)->id;}

void solve()
{
	qsort(q+1,m,sizeof(q[0]),cmp);
	for (int i=1;i<=m;i++)
	{
		for (int j=q[i-1].l;j<q[i].l;j++)
		{
			del(root,j);
			if (a[j].next) insert(root,a[j].next->id);
			else y[a[j].v]=false;
		}
		
		q[i].ans=check(root,q[i].l,q[i].r);
	}
	
	
	
	qsort(q+1,m,sizeof(q[0]),cmp1);
	for (int i=1;i<=m;i++)
	{
		printf("%d\n",q[i].ans);
	}
}

int main()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
	init();
	solve();
	return 0;
}