对于区间修改，区间查询，我们知道有线段树(链状)，RMQ，树状数组，分块，树剖(树形结构)...尽管它们很优秀，但是在处理一些区间问题上，仍然有所不足。
事实上，如果题目不要求在线，存在一种及其优秀的算法：莫队。
什么是莫队？
它由前国家队队长莫涛率先归纳总结，并将其命名为“莫队”。
传说中它是一种“能解决一切区间问题”的算法。
可离线、无修改的莫队
莫队算法其实我们并不陌生，大家在处理区间问题时或多或少使用过莫队的思想。
莫队算法的精髓就是通过合理地对询问排序，然后以较优的顺序暴力回答每个询问。处理完一次询问后，可以使用它的信息得到下一个询问区间的答案。
考虑这个问题：已知区间 [1,5] 的答案，求 [2,6] 的答案，如何暴力去求？
当然，最暴力的做法可以将区间 [2,6] 从头到尾扫一遍；也可以在区间 [1,5] 的基础上，去掉位置1(即将左端点右移一位)，加上位置6(即将右端点右移一位)，得到区间 [2,6] 的答案。
第二种方法好像比前一种方法有所优化，但是具体优化了多少？我们还不知道。但是我们知道，经由“合理的排序”，可以尽可能保证每个点被重复的次数最少，这就是莫队的基本思想。
接下来我们还需要思考一个问题：什么是“合理的排序”？
假设题目给了许多个查询区间，为了保证每个点被重复的次数最少，我们先按照区间左端点从小到大排序；如果左端点相同，那么按照右端点从小到大排序。这样貌似是最好的排序方案了，其实不然，左端点不会“回车”，右端点未必，假设右端点时不时“回车”，这样比起一般暴力，并没有优化多少。
莫队提供了这样一个排序方案：将原序列以√n 为一块进行分块，排序按照上方方案排序。然后我们根据上面提到的“移动当前区间左右端点”的方法，按顺序求每个询问区间的答案，移动每一个询问区间左右端点可以求出下一个区间的答案。
核心代码：
sort(q+1,q+1+m);
int ql=1,qr=0;//初始区间是一个空区间
for(int i=1;i<=m;++i){
while(pl<q[i].l) del(a[pl++];
while(pl>q[i].l) add(a[--pl]);
while(pr<q[i].r) add(a[++pr];
while(pr>q[i].r) del(a[pr--]);
ans[q[i].id]=sum;
}
这样就可以求出答案了！
那么，这样做的复杂度是什么？
显然，每次移动左端点(或右端点)的复杂度都是Ο(1)。那么只需要知道左右端点分别移动了多少次，就可以知道复杂度了。
对于右端点：当当前询问的左端点在同一块时，右端点是有序的，那么右端点最多会从1一直移动到n：两个询问左端点在不同块时(即“跨块”)时，最多从n回到1。两种都是Ο(n)的，总共有根号n块，所以复杂度是O(n根号n)。
对于左端点：当当前询问的左端点在同一块时，注意左端点不是有序的，那么一次最多从块的一段移到另一端，复杂度O(根号n)，总共有n个询问的话，复杂度是O(根号n)。跨块时也类似，移动距离也是O(根号n)。
综上，莫队的复杂度是O(根号n)。
莫队的一大优点是：代码思路及其简单，尤其是序列上无需修改的莫队，核心代码只有短短5行。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,sum;
int a[N],ans[N],cnt[N];
struct query{
int id,l,r;
}q[N];
bool operator(query i,query j){
if(i.l!=j.l) return i.l<j.r;
return i.r<j.r;
}
void add(int x){
if(!cnt[x]) sum++;
cnt[x]++;
}
void del(int x){
cnt[x]--;
if(!cnt[x]) sum--;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
cin>>m;
for(int i=1;i<=m;++i)
q[i].id=i,cin>>q[i].l>>q[i].r;
sort(q+1,q+1+m);
int pl=1,pr=0;
for(int i=1;i<=m;++i){
while(pl<q[i].l) del(a[pl++]);
while(pl>q[i].l) add(a[--pl]);
while(pr<q[i].r) add(a[++pr]);
while(pr>q[i].r) del(a[pr--]);
ans[q[i].id]=sum;
}
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
return 0;
}
可以单点修改的莫队
写完上面这道题，可以发现：普通的莫队算法没有支持修改。那么如何改造该算法使它支持修改呢？
莫队算法被称为“优雅的暴力”，那么我们改造莫队算法的思路也只有一个：改造询问排序的方式，然后继续暴力。
这一次，排序的方式：以
标签：int,复杂度,端点,区间,排序,莫队 From： https://www.cnblogs.com/buleeyes/p/17223994.html