这道题目放在洛谷莫队专题，题解莫队的都过不去，而且也没几个人写莫队，当然我的也过不去。。。本蒟蒻只为了记载点思路。。。
正解貌似是主席树那块的0.0
下面是我的80分垃圾莫队算法（不是莫队垃圾，是我垃圾写不出来）
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <tr1/unordered_map> using namespace std; #define ll long long #define re register const int N=500005; void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } struct note { int l,r,pos,id; bool operator < (const note &x) const { if(x.pos==pos) return r<x.r; else return pos<x.pos; } }a[N]; int b[N]; ll ANS[N],cnt[N]; int vis[1000005]; int main() { int n,m; read(n); for(re int i=1;i<=n;i++) read(b[i]); int siz=sqrt(n); read(m); for(re int i=1;i<=m;i++) { read(a[i].l); read(a[i].r); a[i].id=i; a[i].pos=(a[i].l-1)/siz+1; } sort(a+1,a+1+m); int l=1,r=0; ll ans=0; for(re int i=1;i<=m;i++) { while(l>a[i].l) { l--; if(!vis[b[l]]) ans++; vis[b[l]]++; } while(r<a[i].r) { r++; if(!vis[b[r]]) ans++; vis[b[r]]++; } while(l<a[i].l) { vis[b[l]]--; if(!vis[b[l]]) ans--; l++; } while(r>a[i].r) { vis[b[r]]--; if(!vis[b[r]]) ans--; r--; } ANS[a[i].id]=ans; } for(re int i=1;i<=m;i++) printf("%lld ",ANS[i]); return 0; }