题目背景
无
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
输入样例#1： 复制
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出样例#1： 复制
2
2
4
说明
数据范围：
对于100%的数据，N <= 500000，M <= 200000。
6/28/2018 一个普通的在机房渡过的周四，刚刚学会莫队的我鸡冻的找到了一道自以为的模板题HH的项链 看着博客里别人说“莫队比树状数组快！”
然后
QAQ我可能学了假的莫队QAQ
7/27/2018 ZUTTER终于写出了正解！（撒花）
把询问按照R的顺序排列后，显然同一颜色位置越靠后作用越大。把坐标从1到n扫一遍，每一次扫到一种颜色就把上一次出现这个颜色的位置设为0，本次位置设为1，每次扫到Ri只要用树状数组统计Li到Ri间1的个数即可
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int i,m,n,j=1,k,a[2000001],pre[2000001],c[2000001],s[2000001];
struct vv
{
int l,r,num;
} w[1000001];
bool cmp(vv a,vv b)
{
return a.r<b.r;
}
void add(int k,int z)
{
for(int i=k;i<=n;i+=i & (-i)) c[i]+=z;
}
int ss(int k)
{
int ans=0;
for(int i=k;i>0;i-= i & (-i))
ans+=c[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(i=1;i<=m;i++) scanf("%d%d",&w[i].l,&w[i].r),w[i].num=i;
sort(w+1,w+1+m,cmp);
for(i=1;i<=n;i++)
{
if(pre[a[i]]) add(pre[a[i]],-1);
add(i,1);
pre[a[i]]=i;
while(i==w[j].r) s[w[j].num]=ss(w[j].r)-ss(w[j].l-1),j+=1;
}
for(i=1;i<=m;i++)printf("%d
",s[i]);
}