题意翻译
给出一个长度为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 .
输入格式
- Line 1: n (1 ≤ n ≤ 30000).
- Line 2: n numbers a 1, a 2, ..., a n _ n (1 ≤ a i ≤ 10 ^ 6 ).
- Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
- In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).
输出格式
- For each d-query (i, j), print the number of distinct elements in the subsequence a 1, a i+1 , ..., a j in a single line.
输入输出样例
输入 #1
5
1 1 2 1 3
3
1 5
2 4
3 5输出 #1
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;
}