跳转至

回滚莫队

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

回滚莫队和普通莫队的排序方式基本相同,但不能使用奇偶块优化。这样 \(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;
}

P5386 [Cnoi2019] 数字游戏

题意

给定一个长为 \(n\) 的排列 \(p\),有 \(q\) 次询问,每次询问给定一个整数四元组 \((l, r, a, b)\),表示查询有多少个整数二元组 \((u, v)\) 满足:

  • \(l\le u\le v\le r\)
  • 对于任意 \(\forall u\le i\le v\),有 \(a\le p_i\le b\)

\(n\le 2\times 10^5\)

在区间 \([l,r]\) 内,一段极长的满足 \(p_i\in [a,b]\) 的区间 \([l',r']\) 会产生 \(\frac 12 (len+1)len\) 的贡献。

如果我们使用线段树维护序列,则没法处理值域。两个维度也都不可差分,不能离线扫描线。那么,我们需要使用两个数据结构分别维护序列和值域。

考虑在值域上莫队,现在我们只需要使用序列上的数据结构维护连续段,做到 \(O(1)\) 插入,\(O(\sqrt n)\) 查询区间连续段贡献(假设 \(n,q\) 同阶)即可。由于要求 \(O(1)\) 插入,考虑分块:我们维护块内部的答案和块两侧的极长段长度;查询时枚举整块,处理相邻整块之间的贡献,散块暴力即可。

如何维护连续段呢?我们可以给每个位置维护一个 \(hd\)\(tl\) 表示所在连续段的起始和终止位置。然而,这种维护方式不易实现删除。因此使用回滚莫队,原封不动的恢复数组的改动即可。

代码
#include<iostream>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<iomanip>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int N2 = 500;

int blo[N], blen, bcnt;
int bg[N2], ed[N2];
struct Query {
    int l, r, u, v, id;
    inline bool operator<(const Query &b) const {
        if(blo[u] != blo[b.u]) return blo[u] < blo[b.u];
        return v < b.v;
    }
} qr[N];

int n, q;
int a[N], ia[N];
int ans[N];

ll baoli(int l, int r, int u, int v) {
    int len = 0;
    ll res = 0;
    for(int i = l; i <= r; i++) {
        if(u <= a[i] && a[i] <= v) {
            ++len;
        } else {
            res += (ll)len * (len + 1) / 2;
            len = 0;
        }
    }
    res += (ll)len * (len + 1) / 2;
    return res;
}

// 链表
int sz[N], hd[N], tl[N];
int c_l, c_r, c_ans[N2];
int sta[N], top;

void clear() {
    if(!top) return;
    for(int i = 1; i <= n; i++) hd[i] = tl[i] = i;
    for(int i = 1; i <= bcnt; i++) c_ans[i] = 0;
    for(int i = 1; i <= n; i++) sz[i] = 0;
    top = 0;
}

void insert(int v) {
    int pos = ia[v], bp = blo[pos];
    sta[++top] = pos;
    sz[pos] = 1;
    c_ans[bp] += 1;
    if(pos != bg[blo[pos]] && sz[hd[pos - 1]]) {
        c_ans[bp] += sz[hd[pos - 1]] * sz[pos];
        hd[pos] = hd[pos - 1];
        tl[hd[pos]] = pos;
        sz[hd[pos]] += sz[pos];
    }
    if(pos != ed[blo[pos]] && sz[pos + 1]) {
        c_ans[bp] += sz[pos + 1] * sz[hd[pos]];
        hd[tl[pos + 1]] = hd[pos];
        tl[hd[pos]] = tl[pos + 1];
        sz[hd[pos]] += sz[pos + 1];
    }
}

void roll_back() {
    int pos = sta[top--], bp = blo[pos];
    if(pos != ed[blo[pos]] && sz[pos + 1]) {
        sz[hd[pos]] -= sz[pos + 1];
        tl[hd[pos]] = pos;
        hd[tl[pos + 1]] = pos + 1;
        c_ans[bp] -= sz[pos + 1] * sz[hd[pos]];
    }
    if(pos != bg[blo[pos]] && sz[hd[pos - 1]]) {
        sz[hd[pos]] -= sz[pos];
        tl[hd[pos]] = pos - 1;
        hd[pos] = pos;
        c_ans[bp] -= sz[hd[pos - 1]] * sz[pos];
    }
    assert(sz[pos] == 1);
    c_ans[bp] -= 1;
    sz[pos] = 0;
    hd[pos] = tl[pos] = pos;
}

int query(int l, int r) {
    int res = 0, tmp = 0;
    if(l != bg[blo[l]]) {
        int len = 0;
        for(int i = l; i <= ed[blo[l]]; i++) {
            if(sz[i]) ++len;
            else {
                res += len * (len + 1) / 2;
                len = 0;
            }
        }
        res += len * (len + 1) / 2;
        tmp = len;
        l = bg[blo[l] + 1];
    }
    for(int i = blo[l]; i < blo[r]; i++) {
        res += tmp * sz[bg[i]];
        if(sz[hd[ed[i]]] != blen) tmp = sz[hd[ed[i]]];
        else tmp += sz[hd[ed[i]]];
        res += c_ans[i];
    }
    int len = 0;
    for(int i = r; i >= bg[blo[r]]; i--) {
        if(sz[i]) ++len;
        else {
            res += len * (len + 1) / 2;
            len = 0;
        }
    }
    res += len * (len + 1) / 2;
    res += tmp * len;
    return res;
}

int main() {

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

    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) cin >> qr[i].l >> qr[i].r >> qr[i].u >> qr[i].v;
    for(int i = 1; i <= q; i++) qr[i].id = i;

    for(int i = 1; i <= n; i++) ia[a[i]] = i;

    blen = max((int)3, (int)sqrt(n));
    bcnt = (n + blen - 1) / blen;
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
    for(int i = 1; i <= bcnt; i++) bg[i] = (i - 1) * blen + 1;
    for(int i = 1; i <= bcnt; i++) ed[i] = i * blen;
    ed[bcnt] = n;

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

    for(int i = 1; i <= n; i++) hd[i] = tl[i] = i;

    for(int i = 1; i <= q; i++) {
        int l = qr[i].l, r = qr[i].r, u = qr[i].u, v = qr[i].v, id = qr[i].id;
        if(r - l + 1<= blen) {
            ans[id] = baoli(l, r, u, v);
            continue;
        }
        if(v - u + 1 <= blen) {
            clear();
            c_l = u;
            c_r = u - 1;
            while(c_r < v) insert(++c_r);
            ans[id] = query(l, r);
            while(top) roll_back();
            c_l = 0;
            continue;
        }
        if(c_l <= u) {
            clear();
            c_l = ed[blo[u]] + 1;
            c_r = ed[blo[u]];
        }
        while(c_r < v) insert(++c_r);
        while(c_l > u) insert(--c_l);
        ans[id] = query(l, r);
        while(c_l < ed[blo[u]] + 1) ++c_l, roll_back();
    }

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

    return 0;
}