原本想用莫队水一水
结果只有80分，不够学了一招。
将问题转化为离线问题。
我们先将询问按右节点升序排序。
然后对于每一个值，我们可以肯定的是，只有最靠近询问右端的值才可能起作用。
case 1 ：如果询问不包括某个值。那么这个值，对答案没有影响
case 2 ：包括的话，那么至少包括1个这样的值，而我们询问的是不同的个数，所以对答案也没有影响
这样的话，我们只需要维护最靠右的位置在哪就行了。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct BIT
{
int num;
int data[1000100];
void insert(int value,int pos)
{
while(pos<=num)
{
data[pos]+=value;
pos+=(pos&(-pos));
}
}
int sum(int pos)
{
int ans=0;
while(pos)
{
ans+=data[pos];
pos-=(pos&(-pos));
}
return ans;
}
int check(int l,int r)
{
return sum(r)-sum(l-1);
}
};
BIT bit;
int last[1000100];
int base[500100];
int ans[200100];
struct node
{
int left;
int right;
int num;
};
bool compare(const node &a,const node &b)
{
if(a.right==b.right)
return a.left<b.left;
return a.right<b.right;
}
int read()
{
int s=0,f=1;
char in=getchar();
while(in<'0'||in>'9')
{
if(in=='-')
f=-1;
in=getchar();
}
while(in>='0'&&in<='9')
{
s=(s<<1)+(s<<3)+in-'0';
in=getchar();
}
return s*f;
}
node query[200100];
int main()
{
int n=read();
for(int i=1;i<=n;i++)
base[i]=read();
bit.num=n;
int m=read();
for(int i=1;i<=m;i++)
{
query[i].left=read();
query[i].right=read();
query[i].num=i;//由于是离线操作吗——
}
sort(query+1,query+1+m,compare);//排序，左端点其实可以不拍
int i=0;//i是当前遍历到的右端点
for(int j=1;j<=m;j++)
{
while(i<query[j].right)
{
i+=1;
if(last[base[i]])
{
bit.insert(-1,last[base[i]]);
bit.insert(1,i);
last[base[i]]=i;
}
else
{
bit.insert(1,i);
last[base[i]]=i;
}
}
//printf("%d
",bit.check(query[i].left,query[i].right));
ans[query[j].num]=bit.check(query[j].left,query[j].right);
}
for(i=1;i<=m;i++)
printf("%d
",ans[i]);
}