对询问按照右端点排序,然后 计算按照树状数组求和计算 l,r = sum(r) - sum(l-1)
对a[i] = x , vis[x] = i
当值x没出现过 就add(x,1)
出现过,add(vis[x],-1 ) , add(i,1)
为什么要清除影响,因为你前面先对区间排序, r 递增,计算sum 时递减往前求和
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
struct Q{
int l,r,id;
}q[maxn];
int a[maxn],s[maxn];int n,m;
int ans[maxn],vis[maxn];
int lowbit(int x){
return x&(-x);
}
int query(int x){
int ans = 0;
while(x>0){
ans+=s[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int k){
while(x<=n){
s[x]+=k;
x+=lowbit(x);
}
}
int cmp(Q c,Q d){
return c.r<d.r;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i;
sort(q+1,q+m+1,cmp);
int t=1;
for(int i=1;i<=n;i++){
if(!vis[a[i]])add(i,1),vis[a[i]]=i;
else add(vis[a[i]],-1),add(i,1),vis[a[i]] = i;
while(q[t].r==i){
ans[q[t].id] = query(q[t].r) - query(q[t].l-1);
t++;
}
}
for(int i=1;i<t;i++){
printf("%d\n",ans[i]);
}
return 0;
}