给出一个长度为n 的数列，a1?? a2?? ,...an? ，有q 个询问，每个询问给出数对(i,j)，需要你给出ai??
ai+1?? ，...，aj?? 这一段中有多少不同的数字
English VietnameseGiven a sequence of n numbers a 1 a 2 ..., a n? and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence a i _{i} i? , a i+1 _{i+1} i+1? , ..., a j _{j} j? .
5
1 1 2 1 3
3
1 5
2 4
3 5
3
2
3
思路： 裸的莫队.维护数出现的次数即可
代码：
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 1000000
struct node {
int l,r,pos,id;
bool operator < (const node &a)const
{
if(pos==a.pos)return r<a.r;
return pos<a.pos;
}
}e[N];
int n,m,ta[N],a[N],ans,Ans[N];
int l=1,r=0;
using namespace std;
void add(int x)
{
ta[a[x]]++;
if(ta[a[x]]==1)ans++;
}
void del(int x)
{
ta[a[x]]--;
if(ta[a[x]]==0)ans--;
}
int main()
{
scanf("%d",&n);
int len=sqrt(n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&e[i].l,&e[i].r);
e[i].pos=(e[i].l-1)/len+1;
e[i].id=i;
}
sort(e+1,e+m+1);
for(int i=1;i<=m;i++)
{
while(l<e[i].l)del(l++);
while(r>e[i].r)del(r--);
while(l>e[i].l)add(--l);
while(r<e[i].r)add(++r);
Ans[e[i].id]=ans;
}
for(int i=1;i<=m;i++)printf("%d\n",Ans[i]);
return 0;
}
原文：https://www.cnblogs.com/yelir/p/11574780.html