陈鲁豫体重传说中能解决一切区间处理问题的莫队算法是什么？-信息学竞赛

时间：2016年09月20日 | 作者 : admin | 分类 : 全部文章 | 浏览: 484次

传说中能解决一切区间处理问题的莫队算法是什么？-信息学竞赛
点击上面微信号关注我关注我哟定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！
REC
莫队算法？发明该算法的神犇就就是@莫涛
莫队算法是一个对于区间、树或其他结构离线（在线）维护的算法，此算法基于一些基本算法，例如暴力维护，树状数组，分块胜天湖，最小曼哈顿距离生成树，对其进行揉合从而产生的一个简单易懂且短小好写的算法黛玉晴雯子。此算法在很多情况下可以很轻松的切掉一些复杂而且难写的数据结构问题。

我们一起开看看这个算法的神奇之处吧江南哥！背景
众所周知，在OI竞赛、软件的设计中都会要求我们去处理各种各样的棘手的问题，而这些问题之中，有一大类就是维护问题：比如说对于一个序列的维护娱乐香饽饽，对于棵二叉或者多叉树的维护……这些问题往往会需要我们去使用一个或多个高端的数据结构复合来完美解决，通常题目的代码十分冗长而且出错可能性十分大，是广大OIer、Acmer、Coder所害怕的题目。那么有没有一种方法可以既简单又快捷的解决这类问题（这类问题中的一大部分）呢？莫队算法就诞生辣！算法前提
可以在O(1)的时间内把[l,r]的询问转移到[l-1,r]混世游侠,[l+1,r]杏月是几月,[l,r-1],[l,r+1]的询问，而且不需要修改操作，那么就可以使用莫队算法（[a,b]表示从a到b的区间，包含a和b）算法核心
假如有一个询问[l,r]要转移到一个询问[l1,r1]，那么需要的时间为O(|l1?l|+|r1?r|),在算法前提下，可以用这么多的时间暴力转移。但是可以发现有时候有些点会被来回算很多次，这样大量浪费了时间，所以莫涛大神就想到了一个方法，把这些询问离线的拍一次序，让有些点可以被算的次数少一些。

问题：有n个数组成一个序列，有m个形如询问L, R的询问，每次询问需要回答区间内至少出现2次的数有哪些。
朴素的解法需要读取O(nm)次数。如果数据范围雅迪尔橱柜小，可以用数组，时间复杂度为O(nm)。如果使用STL的Map来保存出现的次数，则需要O(nmlogn)的复杂度。有没有更快的方法呢？
注意到询问并没有强制在线，因此我们可以使用离线方法。注意到一点，如果我们有计算完[L, R]时的“中间变量”（在本题为每个数出现的次数）王国权，那么[L - 1, R]、[L + 1, R]、[L, R - 1]、[L, R + 1]都能够在“中间变量”的“基本操作时间复杂度”(1)得出。如果能安排适当的询问顺序，使得每次询问都能用上上次运行产生的中间变量，那么我们将可以在更优的复杂度完成整个询问。
(1) 如果数据较小，用数组，时间复杂度为O(1)；如果数据较大，可以考虑用离散化或map，时间复杂度为O(logn)。
那如何安排询问呢？这里有个时间复杂度非常优秀的方法：首先将每个询问视为一个“点”，两个点P1, P2之间的距离为abs(L1 - L2) + abs(R1 - R2)，即曼哈顿距离，然后求这些点的最小生成树，然后沿着树边遍历一次盲嫂。由于这里的距离是曼哈顿距离，所以这样的生成树被称为“曼哈顿最小生成树”。最小曼哈顿生成树有专用的算法(2)，求生成树时间复杂度可以仅为O(mlogm)。
(2) 其实这里是建边的算法忒伊亚，建边后依然使用传统的Prim或者Kruskal算法来求最小生成树。
不幸的是，曼哈顿最小生成树的写法很复杂，考场上不建议这样做。　
一种直观的办法是按照左端点排序，再按照右端点排序。但是这样的表现不好。特别是面对精心设计的数据，这样方法表现得很差。
举个例子，有6个询问如下：(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。
这个数据已经按照左端点排序了。用上述方法处理时，左端点会移动6次，右端点会移动移动98+97+95+98+95=483次。右端点大幅度地来回移动，严重影响了时间复杂度——排序的复杂度是O(mlogm)，所有左端点移动次数仅为为O(n)，但右端点每个询问移动O(n)，共有m个询问，故总移动次数为O(nm)，移动总数为O(mlogm + nm)。运行时间上界并没有减少。
其实我们稍微改变一下询问处理的顺序就能做得更好：(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。
左端点移动次数为2+2+1+2+2=9次，比原来稍多。右端点移动次数为2+3+95+3+1=104，右端点的移动次数大大降低了眼泪的上游。
上面的过程启发我们：①我们不应该严格按照升序排序，而是根据需要灵活一点的排序方法；②如果适当减少右端点移动次数，即使稍微增多一点左端点移动次数，在总的复杂度上看，也是划算的。
在排序时笼困，我们并不是按照左右端点严格升序排序询问，而只是令其左右端点处于“大概是升序”的状态。具体的方法是，把所有的区间划分为不同的块，将每个询问按照左端点的所在块序号排序，左端点块一样则按照右端点排序。注意这个与上一个版本的不同之处在于“第一关键字”是左端点所在块而非左端点。
这就是莫队算法。为什么叫莫队算法呢？据说这是2010年国家集训队的莫涛
(3)在作业里提到了这个方法。
(3) 由于莫涛经常打比赛做队长，大家都叫他莫队，该算法也被称为莫队算法。（感谢汝佳大神、莫队的指出）
莫队算法首先将整个序列分成√n个块（同样，只是概念上分的块，实际上我们并不需要严格存储块），接着将每个询问按照块序号排序（一样则按照右端点排序）。之后，我们从排序后第一个询问开始，逐个计算答案。
int len; // 块长度
struct Query{
int L, R, ID, block;
Query(){}// 构造函数重载
Query(int l, int r谭湘君, int ID):L(l), R(r), ID(ID){
block = l / len;
}
bool operator < (const Query rhs) const {
if(block == rhs.block) return R < rhs.R;// 不是if(L == rhs.L) return R < rhs.R; return L < rhs.L
return block < rhs.block; // 否则这就变回算法一了
}
}queries[maxm];
map<int, int> buf;
inline void insert(int n){
if(buf.count(n))
++buf[n];
else
buf[n] = 1;
}
inline void erase(int n){
if(--buf[n] == 0) buf.erase(n);
}
int A[maxn];// 原序列
queue<int> anss[maxm];// 存储答案
int main(){
int n, m;
cin >> n;
len = (int)sqrt(n);// 块长度
for(int i = 1; i <= n; i++){
cin >> A[i];
}
cin >> m;
for(int i = 1; i <= m; i++){
int l, r;
cin >> l >> r;
queries[i] = Query(l, r, i);
}
sort(queries + 1, queries + m + 1);
int L = 1, R = 1;
buf[A[1]] = 1;
for(int i = 1; i <= m; i++){
queue<int>& ans = anss[queries[i].ID];
Query &qi = queries[i];
while(R < qi.R) insert(A[++R]);
while(L > qi.L) insert(A[--L]);
while(R > qi.R) erase(A[R--]);
while(L < qi.L) erase(A[L++]);
for(map<int, int>::iterator it = buf.begin(); it != buf.end(); ++it){
if(it->second >= 2){
ans.push(it->first);
}
}
}
for(int i = 1; i <= m; i++){
queue<int>& ans = anss[i];
while(!ans.empty()){
cout << ans.front() << ' ';
ans.pop();
}
cout << endl;
}
}
尽管分了块陈鲁豫体重，但是我们可以对所有的“询问转移”一视同仁。上述的代码有几个需要注意的地方。
insert和erase，这里在插入前判断了是否存在、插入后判断是否为0，但这不是必须的（insert时会将新节点初始化为0，erase为0后对处理答案不影响）；
区间变化的顺序，谢振南insert最好放在前面，erase最好在后面（想一想，为什么）；
insert总是使用前缀自增自减运算符，erase总是用后缀运算符；
我们在访问我们在“询问转移”前声明了Query的引用，来减少运行时寻址的计算量；
我们重载了Query的构造函数刘依朵。为什么要重载呢？
我们希望在Query得到L, R, ID时自动计算块block步履式挖掘机，这就要写一个构造函数Query(int L, int R, int ID)来实现。但是,当结构体没有构造函数，实例化时不会初始化，有构造函数则一定会调用构造函数进行初始化。“托他的福”，queries数组建立时会对每个元素调用一次构造函数。可是我们只有有3个参数的构造函数，构造时一定要有3个参数。而建立数组时却没有参数，编译器会报错。折中的办法是写一个没有参数的构造函数，可以避免这一问题。
这样排序有个特点。L和R都是“大概是升序”。不过L大概像爬山，总体上升但是会有局部的小幅度下降。R则有些难以形容，大概可以看出其由很多段快速上升，每段上升到顶端后下降到最底。
下面是随机生成100个数据，将数据放到WPS表格后制成图表后的样子。
还有一个问题，为什么分块要分成√n块呢？我们分析一下时间复杂度。
假设我们每k个点分一块。
如果当前询问与上一询问左端点处在同一块，那么左端点移动为O(k)儿玉菜菜子。虽然右端点移动可能高达O(n)，但是整一块询问的右端点移动距离之和也是O(n)（想一想，为什么）。因此平摊意义下，整块移动为O(k) × O(k) + O(n)，一共有n / k块，时间复杂度为O(kn + n2/ k)。
如果询问与上一询问左端点不处于同一块，那么左端点移动为O(k)，但右端点移动则高达O(n)。幸运的是，这种情况只有O(n / k)个，时间复杂度为O(n + n2/ k)。总的移动次数为O(kn + n2 / k)。
因此，当k = √n时，运行时间上界最优，为O( n1.5)。
最后，因此根据每次insert和erase的时间复杂度，乘上O(1)或者O(logn)亦或O(n)不等，得到完整算法的时间复杂度（代码使用了map，为O( logn )）。（本文部分内容参考自网络）
如果想对这种算法了解更多，大家自己搜集一些资料抓紧学习吧，很有用的算法！
信息学竞赛
NOI金牌助你圆梦OI，寒假来NOIP2018冬令营吧~<<<-点击查看详情！

往期精选
清北金牌教研团队助你圆梦OI！
NOIP2017获奖分析-哪些地区哪些学校表现更出色？
全国自主招生高校对各项学科竞赛奖项的要求大汇总!签约路径又有几种方式?从搜狗CEO王小川（信息学金牌），看这二十几年中国奥赛金牌的去向(1)为什么有“编程思维”和数学能力强的人更优秀？
(2)清北独家录制NOIP成功者说学习视频！动手频道！！
(3)NOIP复赛必须记住的30句话！
(4)我们为什么要对孩子进行编程教育？
1.信息学竞赛，你想了解的知识都在这里
2.信息学奥赛（NOIP）初赛学习方法推荐
3.信息学奥赛（NOIP）复赛学习方法推荐
4.信息学竞赛之路
5.大牛为你推荐十本最适合信息学竞赛的书籍
6.信息学奥赛有那么重要吗神无限风流？
7.参加编程竞赛对实际工作的用处
8.清北学堂独家录制NOIP考试技巧讲座
9.在线编程挑战赛第一名：我是这么学算法的
10.最新发布NOI2017 笔试题库
11.信息学竞赛如何学习及准备攻略！
12.NOI 2017获奖名单，几家欢喜几家愁？
13.凭什么我得了信息学奥赛国家一等奖
14.榜样 | 北大降200分要这个诸暨天才少年
15.IOI2017 | 厉害了中国队!!!
16.OI金牌教练胡芳：爱和成长的故事
17.信息学竞赛，一个让孩子不需要再去挤独木桥的方向
18.新学期必须了解的学科竞赛与自主招生时间！
19.北大录取生陈代超：在信息学中找到“思维图谱”
20.国务院发文支持编程教育进入中小学，中国人工智能厚积薄发
重点关注 | NOIP算法总结！
(1)NOIP2017复赛备考攻略-考点分析！
(2)NOIP2017复赛备考攻略-注意事项！
(3)NOIP复赛必须记住的30句话！
(4)NOIP复赛考前时间如何高效利用及考前十点提醒！
(5)NOIP报名，申诉，查成绩方式介绍
(6)NOIP复赛必须记住的30句话！
(7)NOIP复赛考前需要注意的那些事儿小榕软件！！！
(8)NOIP测评环境，数据提交你都了解吗？请注意这些问题！
(9)关于NOI系列赛编程语言使用限制的规定
关注「信息学竞赛」
看更多信息学趣闻与知识
↓↓↓

推荐您阅读更多有关于“”的文章

文章归档