跳转至

回滚莫队

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

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

模板代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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 【模板】回滚莫队&不删除莫队

思路同上。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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\) 表示所在连续段的起始和终止位置。然而，这种维护方式不易实现删除。因此使用回滚莫队，原封不动的恢复数组的改动即可。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#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;
}