回滚莫队

有些问题不支持从序列中删除元素。回滚莫队通过调整扩展的顺序，并增加一些常数，使得删除操作变为回滚（撤销）操作，可以使用栈维护。

回滚莫队和普通莫队的排序方式基本相同，但不能使用奇偶块优化。这样 \(blo[l]\) 相等的所有询问的右端点 \(r\) 就会单调递增。

例题

AT_joisc2014_c 歴史研究

题意

给定一个长为 \(n\) 序列。有 \(q\) 次询问，每次询问给定一个区间 \([l,r]\)，询问 \(\max_{i\in V}\{i\times cnt(i)\}\)。

这种最值形式不易实现删除操作，考虑如何回滚。对于 \(r-l+1\le \sqrt n\) 的询问，直接暴力即可。

考虑左右端点分居两块的情况。记 ed[i] 表示 \(i\) 块的结束位置，初始时 c_l = ed[blo[l]]，c_r = c_l - 1。扩展时总是先处理 \(r\)，然后处理 \(l\)，得到答案后再将 \(l\) 回滚到 ed[blo[l]]。

容易发现时间复杂度仍为 \(O(n\sqrt m)\)，且在块长 \(blen=\frac{n}{\sqrt m}\) 时最优。

模板代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N = 1E5 + 10;

int blen, block[N], ed[N];
struct Query {
    int l, r, id;
    inline bool operator<(const Query& other) const {
        if(block[l] != block[other.l]) return block[l] < block[other.l];
        return r < other.r;
    }
} q[N];

int n, m;
int a[N], num[N], nn = 0;
ll ans[N];

void lisanhua() {
    for(int i = 1; i <= n; i++) {
        num[++nn] = a[i];
    }
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
    }
}

ll cnt[N];
int cl, cr;
ll c_ans;

ll buf[N][2], top;

inline void clear() {
    c_ans = 0;
    // cout << "clear" << endl;
    for(int i = 1; i <= nn; i++) cnt[i] = 0;
}

inline void clear_buf() {
    // cout << "clear buf" << endl;
    top = 0;
}

inline void add(int pos) {
    // cout << "add: " << pos << endl;
    cnt[a[pos]] += num[a[pos]];
    buf[++top][0] = a[pos];
    buf[top][1] = c_ans;
    if(cnt[a[pos]] > c_ans) c_ans = cnt[a[pos]];
}

inline void roll_back() {
    // cout << "roll back" << endl;
    cnt[buf[top][0]] -= num[buf[top][0]];
    c_ans = buf[top--][1];
}

ll bl[N];
inline ll baoli(int l, int r) {
    ll res = 0;
    for(int i = l; i <= r; i++) {
        bl[a[i]] += num[a[i]];
        if(bl[a[i]] > res) res = bl[a[i]];
    }
    for(int i = l; i <= r; i++) {
        bl[a[i]] = 0;
    }
    return res;
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    blen = n / sqrt(m);
    for(int i = 1; i <= n; i++) block[i] = (i + blen - 1) / blen;
    for(int i = 1; i <= n; i++) ed[block[i]] = i;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    lisanhua();

    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r;
        if(block[l] == block[r]) {
            ans[i] = baoli(l, r);
        }
    }

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

    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r;
        if(block[l] == block[r]) {
            continue;
        }
        if(block[l] != block[cl]) {
            cl = ed[block[l]], cr = cl - 1;
            clear();
        }
        while(cr < q[i].r) add(++cr);
        clear_buf();
        while(cl > q[i].l) add(--cl);
        ans[q[i].id] = c_ans;
        while(cl != ed[block[cl]]) roll_back(), ++cl;
    }

    for(int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

P5906 【模板】回滚莫队&不删除莫队

思路同上。

代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2E5 + 10;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

int blen, blo[N], ed[N];
struct Query {
    int l, r, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] != blo[other.l]) return blo[l] < blo[other.l];
        return r < other.r;
    }
} q[N];

int n, m, nn;
int a[N], ans[N];

void lisanhua() {
    int num[N];
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

int b_mn[N], b_mx[N];
int baoli(int l, int r) {
    int res = 0;
    for(int i = l; i <= r; i++) {
        b_mn[a[i]] = min(b_mn[a[i]], i);
        b_mx[a[i]] = max(b_mx[a[i]], i);
        res = max(res, b_mx[a[i]] - b_mn[a[i]]);
    }
    for(int i = l; i <= r; i++) {
        b_mn[a[i]] = INF;
        b_mx[a[i]] = 0;
    }
    return res;
}

int c_l, c_r, c_ans;
int mn[N], mx[N];

int buf[N][4], nb;

void clear_buf() {
    nb = 0;
}

void clear() {
    nb = 0;
    c_ans = 0;
    for(int i = 1; i <= nn; i++) mn[i] = INF, mx[i] = 0;
}

void update(int pos) {
    buf[++nb][0] = a[pos];
    buf[nb][1] = mn[a[pos]];
    buf[nb][2] = mx[a[pos]];
    buf[nb][3] = c_ans;
    mn[a[pos]] = min(mn[a[pos]], pos);
    mx[a[pos]] = max(mx[a[pos]], pos);
    c_ans = max(c_ans, mx[a[pos]] - mn[a[pos]]);
}

void roll_back() {
    int pos = buf[nb][0];
    mn[pos] = buf[nb][1];
    mx[pos] = buf[nb][2];
    c_ans = buf[nb--][3];
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    blen = max(1, (int)(n / sqrt(m)));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
    for(int i = n; i >= 1; i--) ed[i] = (blo[i] == blo[i + 1]) ? ed[i + 1] : i; 

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

    for(int i = 1; i <= nn; i++) mn[i] = b_mn[i] = INF;

    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r;
        if(blo[l] == blo[r]) {
            ans[q[i].id] = baoli(l, r);
            continue;
        }
        if(blo[l] != blo[c_l]) {
            clear();
            c_l = ed[l], c_r = c_l - 1;
        }
        while(c_r < r) update(++c_r);
        clear_buf();
        while(c_l > l) update(--c_l);
        ans[q[i].id] = c_ans;
        while(c_l < ed[c_l]) roll_back(), ++c_l;
    }

    for(int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}