不能分块(显然复杂度会炸啊。。。。。)
离线+BIT。每个颜色在每个询问中只出现一次。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50050
#define maxm 200050
#define maxc 1000500
using namespace std;
int n,a[maxn],aft[maxn],pre[maxn],regis[maxc],ans[maxm],m,p=,t[maxn];
struct query
{
int l,r,id;
}q[maxm];
bool cmp(query x,query y)
{
if (x.l==y.l) return x.r<y.r;
return x.l<y.l;
}
int lowbit(int x)
{
return (x&(-x));
}
void add(int x,int val)
{
for (int i=x;i<=n;i+=lowbit(i))
t[i]+=val;
}
int ask(int x)
{
int ret=;
for (int i=x;i>=;i-=lowbit(i))
ret+=t[i];
return ret;
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d",&a[i]);
pre[i]=regis[a[i]];aft[pre[i]]=i;
regis[a[i]]=i;
}
scanf("%d",&m);
for (int i=;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
for (int i=;i<=n;i++)
{
if (!pre[i]) add(i,);
if (!aft[i]) aft[i]=n+;
}
sort(q+,q+m+,cmp);
for (int i=;i<=m;i++)
{
for (int j=p;j<=q[i].l-;j++)
{
add(j,-);add(aft[j],);
}
p=q[i].l;
ans[q[i].id]=ask(q[i].r)-ask(q[i].l-);
}
for (int i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}