这题一开始我是这样子打的：
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 500010
using namespace std;
struct node{int l,r,fr;}b[N];
int n,m,a[N],st,bl[N];
int tot[N<<1],l,r,ans=0,Ans[N];
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
inline int cmp(node x,node y) {return (bl[x.l]^bl[y.l]) ? bl[x.l]<bl[y.l] : ((bl[x.l] & 1) ? x.r<y.r : x.r>y.r);}
int main()
{
freopen("P1972.in","r",stdin);
// freopen("P1972.out","w",stdout);
n=read(),st=sqrt(n);
for (int i=1;i<=n;i++)
a[i]=read(),bl[i]=(i-1)/st+1;
m=read();
for (int i=1;i<=m;i++)
b[i].l=read(),b[i].r=read(),b[i].fr=i;
sort(b+1,b+m+1,cmp);
l=1,r=0;
for (int i=1;i<=m;i++)
{
while (l<b[i].l) ans-=(! --tot[a[l++]]);
while (l>b[i].l) ans+=(! tot[a[--l]]++);
while (r<b[i].r) ans+=(! tot[a[++r]]++);
while (r>b[i].r) ans-=(! --tot[a[r--]]);
Ans[b[i].fr]=ans;
}
for (int i=1;i<=m;i++)
printf("%d
",Ans[i]);
return 0;
}
结果时超80。。。
为什么？？？因为，数据加强了。。。
这样就真的卡爆了莫队了。。。
所以怎么办呢？
我们来考虑树状数组或线段树。
我们枚举从1到n，在不断右移的情况下，我们记录一下每种贝壳的最后一个出现的位置。
然后以位置做线段树。
我们将询问按右端点从小到大排序。离线做。
对于每个叶子节点，我们记录一下它是否为那种贝壳的最后一个即可，这样保证了答案而且不会重复。
嗯，就这样扫过去，如果当前点i与询问的右端点相等的话，记录一下答案即可。
上标：（线段树版本）（时间1234ms）
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 500010
using namespace std;
struct node{int l,r,fr;}b[N];
int n,m,a[N],las[N<<1],Ans[N],now=1,t[N<<3],x1;
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
inline int cmp(node x,node y) {return x.r<y.r;}
void change(int x,int l,int r,int val,int cg)
{
if (l==r) {t[x]=cg; return;}
int mid=l+r>>1;
if (val<=mid) change(x<<1,l,mid,val,cg);
else change(x<<1|1,mid+1,r,val,cg);
t[x]=t[x<<1]+t[x<<1|1];
}
void find(int x,int l,int r,int fl,int fr)
{
if (fl==l && fr==r) {x1+=t[x]; return;}
int mid=l+r>>1;
if (fr<=mid) find(x<<1,l,mid,fl,fr);
else if (fl>mid) find(x<<1|1,mid+1,r,fl,fr);
else find(x<<1,l,mid,fl,mid),find(x<<1|1,mid+1,r,mid+1,fr);
}
int main()
{
freopen("P1972.in","r",stdin);
freopen("P1972.out","w",stdout);
n=read();
for (int i=1;i<=n;i++) a[i]=read();
m=read();
for (int i=1;i<=m;i++)
b[i].l=read(),b[i].r=read(),b[i].fr=i;
sort(b+1,b+m+1,cmp);
for (int i=1;i<=n;i++)
{
if (las[a[i]]) change(1,1,n,las[a[i]],0);
las[a[i]]=i,change(1,1,n,i,1);
while (i==b[now].r)
x1=0,find(1,1,n,b[now].l,b[now].r),Ans[b[now++].fr]=x1;
}
for (int i=1;i<=m;i++)
printf("%d
",Ans[i]);
return 0;
}
上标：（树状数组版本）（时间653ms）
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 500010
#define lowbit(x) x & (-x)
using namespace std;
struct node{int l,r,fr;}b[N];
int n,m,a[N],las[N<<1],Ans[N],now=1,t[N],x1;
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
inline int cmp(node x,node y) {return x.r<y.r;}
void add(int x,int ad) {for (;x<=n;x+=lowbit(x)) t[x]+=ad;}
int query(int x) {int s=0; for (;x;x-=lowbit(x)) s+=t[x]; return s;}
int main()
{
freopen("P1972.in","r",stdin);
freopen("P1972.out","w",stdout);
n=read();
for (int i=1;i<=n;i++) a[i]=read();
m=read();
for (int i=1;i<=m;i++)
b[i].l=read(),b[i].r=read(),b[i].fr=i;
sort(b+1,b+m+1,cmp);
for (int i=1;i<=n;i++)
{
if (las[a[i]]) add(las[a[i]],-1);
las[a[i]]=i,add(i,1);
while (i==b[now].r)
Ans[b[now].fr]=query(b[now].r)-query(b[now].l-1),now++;
}
for (int i=1;i<=m;i++)
printf("%d
",Ans[i]);
return 0;
}
所以说，树状数组不仅空间小，常数也不大，简直就是强强强啊！！！