Description
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一
段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一
个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只 好求助睿智的你，来解决这个问题。
Input
第一行：一个整数N，表示项链的长度。 第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。 接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。 N ≤
50000，M ≤ 200000。
Output
M行，每行一个整数，依次表示询问对应的答案。
Sample Input
6
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output
2
2
4
【题解】
其实这道题原意是让我练主席树的，但是
好麻烦啊我不想做
那就莫队水过去吧，n*sqrt(n)的时间复杂度是可以跑过去的。。哎呀空间还少了这么多！舒服
题是可以离线离散化的。。但是我好懒，直接开吧那就
同理之前的，分sqrt(n)块，然后莫队处理一下就好
短小精悍的代码yes！
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int v[1110000];
struct node
{int x,y,p;
}a[210000];int n,m,cnt;
int pos[51000],block;
bool cmp(node n1,node n2)
{if(pos[n1.x]>pos[n2.x])return false;else if(pos[n1.x]<pos[n2.x])return true;else return n1.y<n2.y;
}
int e[51000];
void update_d(int x)
{v[e[x]]--;if(v[e[x]]==0)cnt--;
}
void update_a(int x)
{v[e[x]]++;if(v[e[x]]==1)cnt++;
}
int ans[210000];
int main()
{scanf("%d",&n);block=int(sqrt(n));for(int i=1;i<=n;i++){scanf("%d",&e[i]);pos[i]=(i-1)/block+1;}scanf("%d",&m);for(int i=1;i<=m;i++){
scanf("%d%d",&a[i].x,&a[i].y);a[i].p=i;}sort(a+1,a+1+m,cmp);memset(v,0,sizeof(v));cnt=0;for(int i=a[1].x;i<=a[1].y;i++){
if(v[e[i]]==0)cnt++;v[e[i]]++;}int l=a[1].x,r=a[1].y;ans[a[1].p]=cnt;for(int i=2;i<=m;i++){while(l<a[i].x)update_d(l++);while(l>a[i].x)update_a(--l);while(r<a[i].y)update_a(++r);while(r>a[i].y)update_d(r--);ans[a[i].p]=cnt;}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}