莫队
莫队：
1. 离线算法
2. 用于询问不同区间内数值的分布情况
3. 一般不能修改
普通莫队：
假如现在有一个长度为n 的集合，我们称它为a ，有m 次询问，问[Li,Ri] 区间内有多少个不同的数。
我们会这样想：
暴力！暴力！
直接两重循环搞定
for(i=1;i<=m;i++){
int ans=0;
memset(t,0,sizeof(t));
for(j=l[i];j<=r[i];j++){
if(t[a[j]]==0)ans++; //如果这个数之前没出现过，答案加一
t[a[j]]++;//记录每一种数出现了几次
}
cout<<ans<<endl;
}
可如果
那我们就要想一个时间更优的算法
它就是：
莫队！！！
那莫队是什么呢？
就是利用上次询问得到的答案来更新成现在询问要求的答案
形象一点就是这样：
我们要修改的答案就是绿色部分
好像并不难
代码实现如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,t[100010],a[100010],sum,ans[100010];
struct xw{//询问的左右边界
int l,r;
}x[100010];
void jia(int x){//加上当前x位置
if(t[a[x]]==0)sum++;
t[a[x]]++;
}
void jian(int x){//减去当前x位置
t[a[x]]--;
if(t[a[x]]==0)sum--;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>x[i].l>>x[i].r;
}
//输入
int a=1,b=0;//当前已经查询的左(a)右(b)边界(包括a,b)，为了使中间的空间<=0，所以左边界设为1，右边界设为0
for(int i=1;i<=m;i++){
int qx=x[i].l,qy=x[i].r;//当前需要询问的左右边界
while(a<qx){//已经查询的左边界在要查询的左边界的左边，要减去两者中间的一段
jian(a);
a++;
}
while(a>qx){//已经查询的左边界在要查询的左边界的右边，要加上两者中间的一段
a--;
jia(a);
}
while(b<qy){//已经查询的右边界在要查询的右边界的左边，要加上两者中间的一段
b++;
jia(b);
}
while(b>qy){//已经查询的右边界在要查询的右边界的右边，要减去两者中间的一段
jian(b);
b--;
}
//左右边界已经重合，sum为答案
ans[i]=sum;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
//输出
return 0;
}可是如果已经查询的区间和将要查询的区间差距很大，那时间并不理想
所以我们想：能不能改变询问的顺序，让已经查询的区间和将要查询的区间差距缩小，那就好了。
所以我们要加上一个神奇的：
cmp (排序函数):
k=sqrt(n)//分块思想
bool cmp(xw x,xw y){
return x.l/k==y.l/k? x.r/k<y.r/k:x.l/k<y.l/k;//当左边界在同一个块里，按右边界排序，不在同一个块里时，按左边界排序
}它能使时间复杂度最优，但我不记得为什么了
emm————
我们来分析一下时间复杂度：
- 每一个询问：O(n)
- 4个while循环：O(√n)
一共为O(n√n)