对于这类问区间不同数的总数，显然是不能用线段树直接维护的，毕竟不符合区间区间可加性。
考虑对于一个右端点固定的询问，哪些数字实际上是有权值的。
比如区间 1 3 3 2 3 1 2，显然，实际上对于相同的数字，只有一个是有权值的，其他权值均为 \(0\)。但是这样还是无法起到简化的作用，毕竟对于 3 3 3，要选那个 \(3\) 放权值呢？
由于我们固定右端点，所以取最右边的放权值一定可以囊括所有情况。对于上面的例子，我们应该这样放权值：
0 0 0 1 0 1 1
1 3 3 3 1 1 2
答案即为一个区间内的权值之和。
考虑如何实现上述的“固定右端点”，我们可以按照右端点从小到大排序，对其进行离线，对于新加入的右端点（颜色记作 \(col\)），若前面有与 \(col\) 相同的，将那个点的权值减一，这要求先预处理出每个点前面与其颜色相同的点的坐标，并使用树状数组进行单点修改区间查询。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=1e6+10;
int n,m;
int a[N],p[N],lst[N];
int ans[N],tr[N];
struct node {
int l,r,id;
}q[N];
int cmp(node x,node y) {
return x.r<y.r;
}
int lowbit(int x) {
return x&(-x);
}
void add(int nd,int x) {
for(int i=nd;i<=n;i+=lowbit(i)) tr[i]+=x;
}
int query(int nd) {
int sum=0;
for(int i=nd;i;i-=lowbit(i)) sum+=tr[i];
return sum;
}
int main() {
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) {
a[i]=read();
lst[i]=p[a[i]];
p[a[i]]=i;
}
cin>>m;
for(int i=1;i<=m;i++) {
q[i].l=read(); q[i].r=read();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int j=0;
for(int i=1;i<=m;i++) {
while(j+1<=q[i].r) {
j++;
add(j,1);
if(lst[j]) add(lst[j],-1);
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}