题意：给定n个数，m个询问，每次求一段区间内有多少种不同的数。n<=50000,m<=200000
题解：很显然是莫队傻逼题。
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define MAXN 50000 #define MN 200000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,m,size; int s[MAXN+5],pos[MAXN+5],ans[MN+5]; int num[1000005],kind=0; struct ques{int l,r,num;}q[MN+5]; bool cmp(ques x,ques y){return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];} int main() { n=read(); for(int i=1;i<=n;i++)s[i]=read(); m=read();size=sqrt(n); for(int i=1;i<=n;i++)pos[i]=(i-1)/size+1; for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].num=i; sort(q+1,q+m+1,cmp); int l=1,r=1;kind=1;num[s[1]]=1; for(int i=1;i<=m;i++) { while(l<q[i].l) if(!--num[s[l++]]) kind--; while(r>q[i].r) if(!--num[s[r--]]) kind--; while(r<q[i].r) if(++num[s[++r]]==1) kind++; while(l>q[i].l) if(++num[s[--l]]==1) kind++; ans[q[i].num]=kind; } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }