浅谈莫队

莫队是要摸清回滚莫队必须掌握的前置技能(๑ŐдŐ)b
前两天打多校有幸接触了莫队算法，花了几天时间搞懂了这些东西（我菜〒▽〒）

莫队是一个非常强的算法，它主要用于处理区间查询的问题，当区间查询的数量巨大且次数非常多时，普通的暴力查询最差达到O(n^n)的时间复杂度，而利用莫队算法可以大大缩短查询的时间。
莫队其实是利用对查询的离线处理，将查询排序，然后在前一个查询的基础上做数据的修改，道理其实非常简单，可以用一个模拟来代替抽象的言语形容

莫队算法排序小动画

（自己做的很简陋）

将查询分块并进行排序，左边在同一块的对右边排序，左边不在同一块的左边小的排前面。并且将排序后的询问依次进行处理，当处理完一个询问到下一个询问时，在之前的基础上加上比之前多出来的数据，减去比之前少的数据。通常分块的块的大小为 √ n，所以每处理一个询问时间复杂度大多都为√ n，因此总复杂度为O(n√ n),比之前的O(n^n)快了不少。

详细内容我就不说了，对前置技能莫队不了解的可以来看看隔壁此间大佬写的莫队博客

此间大犇yyds

回滚莫队

回滚莫队顾名思义就是 ~~会滚的莫队~~ 回滚的莫队，那么我们为什么要让它滚起来呢？

普通莫队面对大部分的查询我们都需要对查询进行排序，然后依次对排序之后的查询进行处理。处理的时候增加比上一个查询多出来的元素，减去比上一个查询少的元素。但是有些增加元素容易减去元素难的情况或者增加难减去容易的情况，直接莫队打会很麻烦。这个时候就需要想办法尽量减少删除元素的次数，或是直接不删除元素只增加元素。那么这就是回滚莫队的用武之地了。用撤回操作代替删除，然后对询问的排序方式进行修改，使处理查询的时候尽量减少撤回的次数
处理起来很麻烦，这也是一个大量空间换时间的算法

样例

P5906 【模板】回滚莫队&不删除莫队
一道题面非常简单的题

还有的人说AT1219 歴史の研究更像模板题，感兴趣的可以看看

题目描述

给定一个序列，多次询问一段区间 [l,r]，求区间中相同的数的最远间隔距离。

序列中两个元素的间隔距离指的是两个元素下标差的绝对值。

对于 100% 的数据，满足 1≤n,m≤2⋅10 ^ 5 ，1≤ai≤2⋅10 ^ 9。

对这道题而言，增加元素的时候只需更新相应的最右元素的下标，同时更新相应的最左元素的下标，然后用最右边的减去最左边的就可以得出当前元素的最远间隔距离。但是如果减去元素，那就要记录上一个元素，然后在减去元素的同时更改上一个元素，记录上上个元素…非常麻烦。这时利用回滚莫队，减少删除操作，使操作只有增加操作，即可快速且简单地求出询问的答案

个人认为，回滚莫队的精华就在于查询部分，只要搞定这部分，类似的题目做起来易如反掌（

对询问进行分块查询的时候，我们依次对排序之后的查询进行处理，而对于回滚莫队，我们需要排序之后尽量减少删除的次数，这时候我们可以想到，在不同的询问中间取一个点，然后查询方式以这个点为中心向两边延伸，就可以达到只增加不删除的目的。当以这个中心点向两边扩散的询问全部搜完时，我们删除所有临时创建的数据，重新定位下一个中心点，搜下一批的询问。这时我们就避免了删除操作，我们的操作等于撤回之前的所有操作（回到之前没搜过的样子），去处理剩下的所有询问。时间复杂度与普通莫队几乎没有差别，但我们这样做就避免了删除操作。

代码部分（剩余的详细注释都标注在代码里了）
本人小白如有不对欢迎指正ლ(╹◡╹ლ)

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 200010;
struct query {int l, r, id;//询问
}qy[N];
struct ls{int id, x;
}shu[N];
int ans[N], rd[N], R[N], block, Ans1 = 0, Ans2 = 0;
int tagl[N], tagr[N], b[N], ed2[N];
//tagl为元素最左出现的位置，tagr为元素最右出现的位置
bool cmp(query x, query y)//对询问进行排序，左边块相同的右边小的排前面，左边块不同的左边小的排前面
{return (b[x.l] == b[y.l]) ? x.r < y.r : b[x.l] < b[y.l];
}
bool cmp2(ls x,ls y)
{return x.x < y.x;//对输入的数据进行排序，用来离散化处理
}
void insertl(int x) {//插入左端的点if (!ed2[rd[x]])ed2[rd[x]] = x;//ed2为每次询问中的公共起点之前元素最后出现的位置Ans2 = max(Ans2, max(tagr[rd[x]], ed2[rd[x]]) - x);
}
void insertr(int x) {//插入右端的点if (!tagl[rd[x]])tagl[rd[x]] = x;tagr[rd[x]] = x;Ans1 = max(Ans1, x - tagl[rd[x]]);
}
void lsh(int n)//离散化
{sort(shu + 1, shu + n + 1, cmp2);//排序然后离散化int pre = -1, cnt = 0;for (int i = 1; i <= n; i++){if (shu[i].x != pre)cnt++;rd[shu[i].id] = cnt;//替换当前点的数据pre = shu[i].x;}
}
int read() {//快读防卡常int x = 0, f = 1;char c = getchar();while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}
void modui(int m)//开始处理询问 
{int bl = 0, l = 0, r = 0;Ans1 = 0;for (int i = 1; i <= m; i++){if (b[qy[i].l] == b[qy[i].r])//如果l和r的块相同那么直接暴力求答案就可以了{for (int j = qy[i].l; j <= qy[i].r; j++)tagl[rd[j]] = 0;//暴力循环之前将之前临时存的数据清零for (int j = qy[i].l; j <= qy[i].r; j++)//非常的暴力{if (!tagl[rd[j]])tagl[rd[j]] = j;ans[qy[i].id] = max(ans[qy[i].id], j - tagl[rd[j]]);}for (int j = qy[i].l; j <= qy[i].r; j++)tagl[rd[j]] = 0;continue;}int now = b[qy[i].l];//now为当前l的块if (bl != now)//如果不在一个块中则清空之前临时储存的数据，重置l和r{Ans1 = 0;for (int j = l; j <= r; j++)tagl[rd[j]] = tagr[rd[j]] = 0;l = R[now];//l定义为当前所属的块的最右边r = l - 1; bl = now;}while (r < qy[i].r)insertr(++r);//紧张刺激的莫队环节int p = l; Ans2 = 0;while (p > qy[i].l)insertl(--p);while (p < l){ed2[rd[p]] = 0;p++;}//循环结束之后重置ed2ans[qy[i].id] = max(Ans1, Ans2);//最后对比一下两端的答案即为最终答案}
}
int main()
{int n, m;scanf("%d", &n);block = pow(n, 0.5);//对块的大小进行定义，一般是取√ n，跟普通莫队无异for (int i = 1; i <= n; i++) {//输入数据shu[i].x = read();shu[i].id = i;b[i] = (i - 1) / block + 1;//存储块信息（减少计算量，不然每次都要计算一个l/block浪费时间）}for (int i = 1; i <= b[n]; i++)//处理出每个块的右端，存在R中 R[i] = (i == b[n]) ? n : block * i;lsh(n);//因为数据到10^9，而总共只有2*10^5，因此我们可以对数据进行离散化处理（这题有点卡常，能减少时间就尽量减）scanf("%d", &m);for (int i = 1; i <= m; i++) {qy[i].l = read(), qy[i].r = read(); qy[i].id = i;//输入询问数据，id记录询问顺序}sort(qy + 1, qy + 1 + m, cmp);//对询问进行离线处理modui(m);//莫队部分for (int i = 1; i <= m; i++)printf("%d\n", ans[i]);//按原本顺序输出答案}