不是裸题，鉴定完毕。

我是题面

对于这道题，我是离线做的。。。

树状数组吧，好些点

我们可以很轻易地得到一个很显然的结论，就是关于同一个数，我们只需要记录它不超过当前区间的最后一次出现的位置即可。举例，假设一个区间为[l,5]，数字分别为1,2,3,1,4，那么无论l取几，只要包含了第4个数"1"，"1"这个数也就出现过了，不必管之前的"1"在哪里

那么我们记录一个数最后出现的位置，将区间按右端点从小到大排序，若每次只更新到当前区间的右端点，if(更新到的数出现过)则将上一次出现的位置的tree--;当前位置的tree++，更新完就区间查询存储答案，最后将查询恢复排序输出答案即可

上代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc() getchar()

#define maxn 500005

using namespace std;

inline ll read(){

	ll a=0;int f=0;char p=gc();

	while(!isdigit(p)){f|=p=='-';p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}

void write(ll a){

	if(a>9)write(a/10);

	putchar(a%10+'0');

}

int n,m,a[maxn],b[1000005];

struct ahaha{

	int l,r,ans,zz;

}q[maxn>>1];

inline bool cmp1(ahaha x,ahaha y){

	return x.r<y.r;

}

inline bool cmp2(ahaha x,ahaha y){

	return x.zz<y.zz;

}

#define lowbit(i) i&-i

int tree[maxn];

inline void update(int x,int z){

	while(x<=n){

		tree[x]+=z;

		x+=lowbit(x);

	}

}

inline int query(int x){

	int ans=0;

	while(x){

		ans+=tree[x];

		x-=lowbit(x);

	}

	return ans;

}

int main(){

	n=read();

	for(int i=1;i<=n;++i)a[i]=read();

	m=read();

	for(int i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].zz=i;

	sort(q+1,q+m+1,cmp1);

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

		for(int j=q[i-1].r+1;j<=q[i].r;++j){

			if(b[a[j]])update(b[a[j]],-1);

			b[a[j]]=j;update(b[a[j]],1);

		}

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

	}

	sort(q+1,q+m+1,cmp2);

	for(int i=1;i<=m;++i)write(q[i].ans),putchar('\n');

	return 0;

}