AC版本。

#include<bits/stdc++.h>
//#pragma GCC optimze(2)
using namespace std;

const int N=4e7;
int n,m,pos,lst;
int ls[N],rs[N],t[N],root[N>>3],now[N>>3],ans[N>>3];
struct node
{
	int l,r,id;
}q[N>>3];
bool cmpr(node a,node b){return a.r<b.r;} 
int read()
{
	char ch=getchar();int x=0;
	while(!isdigit(ch)){ch=getchar();} 
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x;
}
void write(int a)
{
	if(a>9)write(a/10);
	putchar(a%10+'0');
}
void pushup(int rt)
{
	t[rt]=t[ls[rt]]+t[rs[rt]];
}
void add(int rt,int &ne,int l,int r,int a,int b)
{
	if(rt<=lst)ne=++pos;
	else ne=rt;
	if(l==r)
	{
		t[ne]=t[rt]+b;
		return ;
	}
	int mid=(l+r)>>1;
	if(a<=mid)add(ls[rt],ls[ne],l,mid,a,b),rs[ne]=rs[rt];
	else add(rs[rt],rs[ne],mid+1,r,a,b),ls[ne]=ls[rt];
	pushup(ne);
}
int qury(int rt,int l,int r,int a,int b)
{
	if(a<=l&&r<=b)return t[rt];
	int mid=(l+r)>>1;
	int res=0;
	if(a<=mid)res+=qury(ls[rt],l,mid,a,b);
	if(b>mid)res+=qury(rs[rt],mid+1,r,a,b);
	return res;
}

int main()
{
	n=read();
	for(int i=1,ai;i<=n;i++)
	{
		ai=read();lst=pos;
		if(now[ai])add(root[i-1],root[i],1,n,now[ai],-1),add(root[i],root[i],1,n,i,1);
		else add(root[i-1],root[i],1,n,i,1);
		now[ai]=i;
	}
	cerr<<clock();
	m=read();
	for(int i=1,l,r;i<=m;i++)
	{
		l=read(),r=read();
		q[i].id=i;
		q[i].l=l;
		q[i].r=r;
//		write(qury(root[r],1,n,l,r));我修改掉的部分
//		putchar('\n');
	}
	sort(q+1,q+m+1,cmpr);//新加入了排序询问
	for(int i=1;i<=m;i++)
		ans[q[i].id]=qury(root[q[i].r],1,n,q[i].l,q[i].r);
	for(int i=1;i<=m;i++)write(ans[i]),putchar('\n');		
	return 0;
}

T飞版本。

#include<bits/stdc++.h>
using namespace std;

const int N=4e7;
int n,m,pos,lst;
int ls[N],rs[N],t[N],root[N>>3],now[N>>3];
int read()
{
	char ch=getchar();int x=0;
	while(!isdigit(ch)){ch=getchar();} 
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x;
}
void write(int a)
{
	if(a>9)write(a/10);
	putchar(a%10+'0');
}
void pushup(int rt)
{
	t[rt]=t[ls[rt]]+t[rs[rt]];
}
void add(int rt,int &ne,int l,int r,int a,int b)
{
	if(rt<=lst)ne=++pos;
	else ne=rt;
	if(l==r)
	{
		t[ne]=t[rt]+b;
		return ;
	}
	int mid=(l+r)>>1;
	if(a<=mid)add(ls[rt],ls[ne],l,mid,a,b),rs[ne]=rs[rt];
	else add(rs[rt],rs[ne],mid+1,r,a,b),ls[ne]=ls[rt];
	pushup(ne);
}
int qury(int rt,int l,int r,int a,int b)
{
	if(a<=l&&r<=b)return t[rt];
	int mid=(l+r)>>1;
	int res=0;
	if(a<=mid)res+=qury(ls[rt],l,mid,a,b);
	if(b>mid)res+=qury(rs[rt],mid+1,r,a,b);
	return res;
}

int main()
{
	n=read();
	for(int i=1,ai;i<=n;i++)
	{
		ai=read();lst=pos;
		if(now[ai])add(root[i-1],root[i],1,n,now[ai],-1),add(root[i],root[i],1,n,i,1);
		else add(root[i-1],root[i],1,n,i,1);
		now[ai]=i;
	}
	m=read();
	for(int i=1,l,r;i<=m;i++)
	{
		l=read(),r=read();
		write(qury(root[r],1,n,l,r));
		putchar('\n');
	}
	return 0;
}