一眼莫队
然而莫队就只有32分
莫队毕竟是O(n根号n)的，肯定过不了
我们思考一个区间[l,r]，我们发现，如果从r开始往l数，那么每种数字只有最右边的那个才有意义，如：
1 1 4 5 1 4
[1,5]很明显对于1来说，只有在4这个下标的1才有意义
所以我们可以先求出每个数第一个从右往左数和他一样的数
然后对于询问进行排序（离线），然后每次按照顺序进行插入就ok了
如上面那个例子
插入（1，1）
删除（1，1）
插入（2，1）
插入（3，1）
插入（4，1）
删除（2，1）
插入（5，1）
回答 求和（1，5）-求和（1，1-1）
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
using namespace std;
int z[5000005],s[5000005];
int nex[5000005];
int cnt;
int n,m;
struct node{
int l;
int r;
int ans;
int id;
}a[5000005];
bool cmp(node x,node y)
{
return x.r<y.r;
}
bool cmp2(node x,node y)
{
return x.id<y.id;
}
int lb(int x)
{
return x&-x;
}
void xg(int x,int k)
{
while(x<=n)
{
s[x]+=k;
x+=lb(x);
}
}
int qh(int y)
{
int ans=0;
while(y)
{
ans+=s[y];
y-=lb(y);
}
return ans;
}
int main()
{
scanf("%d",&n);
for1(i,1,n) scanf("%d",&z[i]);
cin>>m;
for1(i,1,m)
scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
sort(a+1,a+m+1,cmp);
cnt=1;
for1(i,1,m)
{
int qr=a[i].r;
for1(j,cnt,qr)
{
if(nex[z[j]])
xg(nex[z[j]],-1);
xg(j,1);
nex[z[j]]=j;
}
cnt=qr+1;
a[i].ans=qh(a[i].r)-qh(a[i].l-1);
}
sort(a+1,a+m+1,cmp2);
for1(i,1,m)
{
printf("%d\n",a[i].ans);
}
return 0;
}