难题，所以会讲得细一些。
首先我们想如何统计区间[l,r]内不同贝壳的个数。
第一个思路就是线段树/树状数组，query(1,r)-query(1,l-1)对不对？
然而这样是不对的。
然后我们举个例子：
例如有一段区间是[ 1 2 3 1 2 3 1 2 3 ]这样子，如果要统计不同贝壳的个数，那么一个贝壳就可以代表所有同色贝壳。
也就是说，假设要统计这个区间内1有没有出现，那这个区间变成这样子：[ 1 2 3 0 2 3 0 2 3 ] 或 [ 0 2 3 1 2 3 1 2 3 ] 或什么样子，都是一样的，只要1出现过一次，那就说明1出现过了。
所以可以把所有询问按左端点排序，左端点相同的按照右端点排序，然后挨个统计：
设next[ j ] 表示：x为j位置贝壳的颜色，next[j]表示的就是j后面第一个颜色为x的位置。如在我们举的例子中，next[1]=4，next[2]=5，next[5]=8。
然后我们在刚开始初始化的时候，只有所有颜色第一次出现的位置作为该颜色的代表贝壳，也就是说只有这几个位置有1个不同的贝壳。
然后在扫描询问数组的时候，把q[i-1].l到q[i].l之间的不同贝壳个数更新。具体方法是把next[当前位置]所指向的位置不同的贝壳变成1。
这样就可以树状数组查询了。
#include<cstdio> #include<cstdlib> #include<cctype> #include<cstring> #include<algorithm> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct line{ int l,r,id,ans; bool operator <(const line &a)const{ if(l!=a.l) return l<a.l; return r<a.r; } }q[1000100]; bool cmp(line a,line b){ return a.id<b.id; } int n; int tree[1000100]; inline void add(int pos){ while(pos<=n){ tree[pos]++; pos+=pos&(-pos); } } inline int query(int pos){ int ans=0; while(pos){ ans+=tree[pos]; pos-=pos&(-pos); } return ans; } int pre[1001010]; int next[1001010]; int vis[1001010]; int que[1001010]; int main(){ n=read(); for(int i=1;i<=n;++i){ que[i]=read(); next[pre[que[i]]]=i; if(!pre[que[i]]){ add(i); vis[i]=1; } pre[que[i]]=i; } int m=read(); for(int i=1;i<=m;++i) q[i]=(line){read(),read(),i}; std::sort(q+1,q+m+1); q[0].l=1; for(int i=1;i<=m;++i){ if(q[i-1].l!=q[i].l) for(int j=q[i-1].l;j<q[i].l;++j) if(next[j]&&!vis[next[j]]){ vis[next[j]]=1; add(next[j]); } q[i].ans=query(q[i].r)-query(q[i].l-1); } std::sort(q+1,q+m+1,cmp); for(int i=1;i<=m;++i) printf("%d ",q[i].ans); return 0; }