前置知识: 基础莫队

$回滚莫队$

$简介$

回滚莫队又称不删除莫队

用于维护一些不删除属性的操作

例如最大值，加入一个数后只需取一次max，删除一个数却很难维护

$基本操作$

给定长度为$n$的序列

可支持以下$1$种操作：、
1. l r询问$[l,r]$中的某种不删除属性

$排序标准$

1. 按左端点所在块编号,从左到右排序
2. 若左端点所在快相同,比较右端点,从左到右排序

$Code$

bool cmp(Node a, Node b)
{
    int al = get(a.l), bl = get(b.l);
    if (al != bl)return al < bl;
    return a.r < b.r;
}

$思想$

设序列长度为$n$，每块长度为$a$，共有$\frac{n}{a}$块,$m$次询问

1. 循环$1\leq i \leq \frac{n}{a}$，找到所有左端点在第$i$块的询问$l$，$r$
2. 若$r$也在第$i$块,那么就暴力求,时间复杂度$O(am)$
3. 否则，右端点用指针$j$维护，左端点每次回到第i块的右端，暴力求，时间复杂度$O(am+\frac{n^2}{a})$

总时间复杂度 $O(am+\frac{n^2}{a})$

$Code$

以洛谷P5906为例

#include <bits/stdc++.h>
using namespace std;

const int N = 200010, INF = 2e9;
int n, m, len;
int w[N], ans[N];
int first[N], last[N];
int rfirst[N], rlast[N];
vector<int> nums;
struct Node {
    int id, l, r;
}q[N];

int get(int i)
{
    return i / len;
}

bool cmp(Node a, Node b)
{
    int al = get(a.l), bl = get(b.l);
    if (al != bl)return al < bl;
    return a.r < b.r;
}

void add(int x, int& res, int a[N], int b[N], int flag)
{
    a[w[x]] = min(a[w[x]], x);
    b[w[x]] = max(b[w[x]], x);
    res = max(res, b[w[x]] - a[w[x]]);
    if (flag)res = max(res, rlast[w[x]] - a[w[x]]);
}

int main()
{
    scanf("%d", &n);
    len = sqrt(n);

    for (int i = 1; i <= n; i ++ )scanf("%d", &w[i]), nums.push_back(w[i]);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; i ++ )
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();  

    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }

    sort(q + 1, q + m + 1, cmp);

    memset(first, 0x3f, sizeof first);
    memset(last, 0, sizeof last);   
    for (int x = 1; x <= m;)
    {
        memset(rfirst, 0x3f, sizeof first);
        memset(rlast, 0, sizeof last);
        int y = x;
        while (y <= m && get(q[x].l) == get(q[y].l))y ++ ;
        int right = get(q[x].l) * len + len - 1;
        while (x < y && q[x].r <= right)//段内暴力
        {
            int res = 0;
            int id = q[x].id, l = q[x].l, r = q[x].r;
            for (int i = l; i <= r; i ++ )add(i, res, first, last, 0);
            ans[id] = res;
            for (int i = l; i <= r; i ++ )first[w[i]] = INF, last[w[i]] = 0;
            x ++ ;
        }
        int res = 0;
        int i = right + 1, j = right;
        while (x < y)
        {
            int id = q[x].id, l = q[x].l, r = q[x].r;
            while (j < r)j ++ , add(j, res, rfirst, rlast, 0);
            int backup = res;//备份
            while (i > l)i -- , add(i, res, first, last, 1);
            ans[id] = res;
            while (i < right + 1)first[w[i]] = INF, last[w[i]] = 0, i ++ ;//回滚        
            res = backup;
            x ++ ;
        }
    }

    for (int i = 1; i <= m; i ++ )printf("%d\n", ans[i]);

    return 0;
}