数据结构 —— 莫队算法 —— 带修莫队

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构 —— 莫队算法 —— 带修莫队，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2474字，纯文字阅读大概需要4分钟。

内容图文

【概述】

普通莫队由于强制离线是不能修改的，但对于强制在线的题，可以在普通莫队的基础上强行加上一维时间轴 time，表示这次操作的时间，即在每个询问前已经完成了多少次修改。

简单来说，就是将询问 [l,r]，变为 [l,r,time]，那么指针也可在时间维度上移动，使得第一关键字是左端点所在的块，第二关键字是右端点所在的块，第三关键字是时间，即 [l,r,time] 多了一维可移动的方向：

• [l-1,r,time]
• [l+1,r,time]
• [l,r-1,time]
• [l,r+1,time]
• [l,r,time-1]
• [l,r,time+1]

暴力查询时，如果当前修改数比询问的修改数少就把没修改的进行修改，反之回退，需要注意的是，修改分为两部分：

• 若修改的位置在当前区间：更新答案
• 无论修改的位置是否在当前区间：都要进行修改，以供 add 和 del 函数在以后更新答案

int l=0,r=0,time=0;
for(int i=1;i<=m;++i){
    int ql=q[i].l,qr=q[i].r;
    while(time<q[i].time)  change(++time);//[l,r,time+1]
    while(time>q[i].time)  change(time--);//[l,r,time-1]
    while(l>ql) add(--l);//[l-1,r]
    while(l<ql) del(l++);//[l+1,r]
    while(r<qr) add(++r);//[l,r+1]
    while(r>qr) del(r--);//[l,r-1]
    res[q[i].id]=ans;//存储答案
}

【排序】

由于第一关键字是左端点所在的块，第二关键字是右端点所在的块，第三关键字是时间，虽然多了一个维度，但转移仍是 O(1) 的复杂度，只需要在排序时考虑 time 的影响即可。

• 当左右端点在同一个块中：以 time 为关键字排序
• 当左端点在同一个块中，右端点不在：以右端点为关键字排序
• 当左端点不在同一个块：以左端点为关键字排序

bool cmp(Node a,Node b){//排序
    if( (a.l/block)==(b.l/block) ){//当左端点位于同一个块时
        if( (a.r/block)==(b.r/block) )//当右端点位于同一个块时
            return a.time<b.time;
        else
            return a.r<b.r;
    }
    else//当左端点不位于同一个块时
        return a.l<b.l;
    //return (a.l/block)^(b.l/block) ? a.l<b.l : ( ((a.r/block)^(b.r/block))?a.time<b.time:a.r<b.r );
}

【分块与时间复杂度】

设 block 为分块大小，c 为修改个数，q 为询问个数，l、r 块表示以 l/block、r/block 分的块，每个 l 块包含 n/block 个 r 块

• 对于时间指针 time，每个 r 块最多会移动 c 次，共有  个 r 块，总移动次数为 
• 对于左端点指针 l：l 块内最多移动 block 次，换 l 块时最多移动 2*block 次，总移动次数为：
• 对于右端点指针 r：总移动次数为：
  • r 块内最多移动 block 次，换 r 块时最多移动 2*block 次，所有 l 块内移动次数之和为 
  • 换 l 块时最多移动 n 次，总的换 l 块时移动次数之和为 

故总移动次数为：，因而总时间复杂度为 

由于一般题目不会分别告诉修改与询问的个数，统一用 m 表示，则有：

通过 Mathermatica 软件分析，要想让总时间复杂度最小，可以得到 block 的取值如下：

由于式子过于复杂，难以写出带修莫队的最佳分块数，因此一般视作 n=m，即有：

令总时间复杂度最小，可得到当  时最小，此时总时间复杂度为：

综上，分块一般以  为一块，分成  个块，总时间复杂度为：

int block=pow(n,0.66666);

 【模版】

内容总结

以上是互联网集市为您收集整理的数据结构 —— 莫队算法 —— 带修莫队全部内容，希望文章能够帮你解决数据结构 —— 莫队算法 —— 带修莫队所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---