回滚莫队-笔记 /「AtCoder 1219」歴史の研究-题解

通过AtCoder 1219 歴史の研究这道题目来学习一下 回滚莫队
回滚莫队 适用于容易进行add操作,而不容易实现del的情况

通过莫队的分块,指针移动的思想,可以让左指针进行回滚操作, 近似 达到del的效果

回滚莫队

思想

由于莫队对所有询问离线排序后,当左端点在同一个块内时,右端点递增
所以对于每个块,右指针直接向右依次执行add操作即可

对于左指针,在一个块内时,可以每次都从块的右边界向左进行add,由于不方便进行del操作,所以可以先记录下左指针在右边界时的Ans,然后每次向左移动到q[i].l时,将左指针再移回右边界,并且将Ans回滚到移动之前的值。由于分块,这样做的复杂度也不会很大

综上,对于每个块,右指针依次向右推进,左指针在右边界和查询的左端点之间反复横跳
这样,执行的就只剩add操作,通过左指针的横跳,避免了del操作

注意,当左右端点都在同一个块时,只要暴力求出结果就可以了
一定要注意: 不要使用奇偶排序,必须保证右端点的 单调递增

对于每个块内的处理,大概如下图:
橙色箭头:左指针的移动 蓝色箭头:右指针的移动

时间复杂度

时间复杂度由以下几个方面组成

  1. 询问排序
  2. 同一个块内的暴力求解
  3. 左指针的移动(横跳)
  4. 右指针的顺次移动

下面来 不严谨 简要地计算一下时间复杂度

  1. 排序:$O(n\log n)$
  2. 暴力:暴力的区间最长为$\sqrt{n}$,所以单次暴力的复杂度为$O(\sqrt{n})$,$n$次暴力的复杂度为$O(n\sqrt{n})$其实到不了n次
  3. 左指针移动: 进行add操作的复杂度为$O(1)$,块长$\sqrt{n}$,每次左移最坏复杂度$O(\sqrt{n})$,回滚时仍需要$O(\sqrt{n})$清除贡献
    所以对于所有块,一共要移动$q$次,总的复杂度为$O(2q\sqrt{n})$
  4. 右指针移动: 对于每个块,最坏只要移动$n$次,一共$\sqrt{n}$个块,所以复杂度为$O(n\sqrt{n})$

综上,总的复杂度为$O(n\log n)+O(2q\sqrt{n})+O(n\sqrt{n})\ \sim\ O(n\sqrt{n})$

针对$\mathcal{AT1219}$的具体实现

添加贡献的add操作很容易实现

1
2
3
4
void add(int x) {
cnt[a[x]]++;
Ans = max(Ans, 1LL * cnt[a[x]] * old[a[x]]);
}

同一块内的暴力也很容易实现

1
2
3
4
5
6
7
8
9
LL solve(int l, int r) {
LL res = 0;
for (int i = l; i <= r; ++i) cnt2[a[i]] = 0;
for (int i = l; i <= r; ++i) {
cnt2[a[i]]++;
res = max(res, 1LL * cnt2[a[i]] * old[a[i]]);
}
return res;
}

其余情况下根据前面所说,可以实现

1
2
3
4
5
6
while (r < q[i].r) add(++r);  // 右指针右移,添加贡献
LL tmp = Ans; // 记录左指针移动前的答案
while (l > q[i].l) add(--l); // 左指针左移,添加贡献
ans[q[i].id] = Ans;
while (l < rpos[k] + 1) cnt[a[l++]]--; // 左指针移动回右边界,并途中删除对cnt的贡献
Ans = tmp; // 回滚到移动前的答案

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
int x = 0; int f = 1; char ch = getchar();
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x * f;
}

const int maxn = 100010;

int n, m, len, l, r;
int a[maxn], cnt[maxn], rpos[maxn], old[maxn], cnt2[maxn];
LL Ans, ans[maxn];

struct Query {
int l, r, id, pos;
}q[maxn];
bool cmp(Query a, Query b) {
if (a.pos != b.pos) return a.pos < b.pos;
return a.r < b.r;
}

LL solve(int l, int r) {
LL res = 0;
for (int i = l; i <= r; ++i) cnt2[a[i]] = 0;
for (int i = l; i <= r; ++i) {
cnt2[a[i]]++;
res = max(res, 1LL * cnt2[a[i]] * old[a[i]]);
}
return res;
}

void add(int x) {
cnt[a[x]]++;
Ans = max(Ans, 1LL * cnt[a[x]] * old[a[x]]);
}

int main() {
n = read(); m = read(); len = sqrt(n); int num = ceil((double)n / len);
for (int i = 1; i <= num; ++i) rpos[i] = len * i; rpos[num] = n;
for (int i = 1; i <= n; ++i) old[i] = a[i] = read();
sort(old + 1, old + 1 + n);
int len_ = unique(old + 1, old + 1 + n) - old - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound(old + 1, old + 1 + len_, a[i]) - old;
for (int i = 1; i <= m; ++i) {
q[i].l = read(); q[i].r = read();
q[i].id = i; q[i].pos = (q[i].l - 1) / len + 1;
}
sort(q + 1, q + 1 + m, cmp); l = 1;
for (int k = 1, i = 1; k <= num; ++k) {
l = rpos[k] + 1, r = rpos[k], Ans = 0;
memset(cnt, 0, sizeof(cnt));
while (q[i].pos == k) {
if (q[i].l / len == q[i].r / len) {
ans[q[i].id] = solve(q[i].l, q[i].r);
i++; continue;
}
while (r < q[i].r) add(++r);
LL tmp = Ans;
while (l > q[i].l) add(--l);
ans[q[i].id] = Ans;
while (l < rpos[k] + 1) cnt[a[l++]]--;
Ans = tmp; i++;
}
}
for (int i = 1; i <= m; ++i) {
printf("%lld\n", ans[i]);
}
return 0;
}

回滚莫队-笔记 /「AtCoder 1219」歴史の研究-题解

https://blog.tonycrane.cc/p/7d7b5548.html

作者

TonyCrane

发布于

2020-04-30

更新于

2020-05-05

许可协议

评论