【学习笔记】回滚莫队

大概是一种离线算法,用于巧妙维护没有删除操作的离线序列问题。一般情况下都可以转化成普通的莫队带一个 ds 的 $\log$ 做法,可以比较简单地去维护某些不能差分的操作(即 del 比较难以实现,比如 $\max$)。

考虑不同于普通莫队的另一种做法。

首先还是将所有询问排序。考虑一种根号分治的做法:

  • 对于两个端点在同一个块内的直接跑暴力,总复杂度是 $O(qB)$;

  • 两个端点不在一个块内的,考虑把两个指针都指针移到下一个块的开头,途中对每个点只撤销贡献而不删除贡献,之后 $r$ 单调向右移,$l$ 向左移,添加过程中计算贡献——其中控制 $r$ 单增的原因是 $r$ 的移动步长是 $O(n)$ 的,但每次 $l$ 的移动步长是 $O(B)$ 的。

这样的话,复杂度就是 $O(qB+\frac{n^2}{B})$ 。简单地均值一下发现还是 $O(n\sqrt q)$ 的。

那看上去除了复杂度分析很莫队,本质上就是个根号分治啊。

AT1219 歴史の研究

给定一堆事件:

  1. 选择日记中连续的一些天作为分析的时间段
  2. 事件种类 $t$ 的重要度为 $t$ $\times$ (这段时间内种类为 $t$ 的事件数)。
  3. 计算出所有事件种类的重要度,输出其中的最大值 现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值.

发现插入很简单,但是由于求的是 $\max$,所以朴素地删除会让答案难以统计。于是考虑直接上回滚莫队。

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
struct qs{ 
int l, r, id ;
}q[M] ;
LL res ;
int g[N] ;
LL ans[M] ;
int buc[M] ;
int blg[N] ;
int L[N], R[N] ;
int base[N], t[N] ;
int n, w, m, b, bnum ;

inline bool comp(qs p1,qs p2){
if (blg[p1.l] ^ blg[p2.l] )
return blg[p1.l] < blg[p2.l];
else return p1.r < p2.r ;
}
void del(int p){ buc[base[p]] -- ; }
void add(int p, LL & ret){
buc[base[p]] ++ ;
ret = max(ret, 1ll * buc[base[p]] * g[p]) ;
}
int bucc[N] ;
LL brute_force(int l, int r){
LL ret ; ret = 0 ;
for (int i = l ; i <= r ; ++ i) bucc[base[i]] ++ ;
for (int i = l ; i <= r ; ++ i)
ret = max(ret, 1ll * bucc[base[i]] * g[i]) ;
for (int i = l ; i <= r ; ++ i) bucc[base[i]] -- ;
return ret ;
}
int main(){
cin >> n >> m ; int l, r, lb ;
b = sqrt(1.0 * n) ; bnum = n / b + 1 ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &g[i]), t[i] = g[i] ;
for (int i = 1 ; i <= bnum ; ++ i)
L[i] = (i - 1) * b + 1, R[i] = i * b ;
R[bnum] = min(R[bnum], n) ;
for (int i = 1 ; i <= bnum ; ++ i)
for (int j = L[i] ; j <= R[i] ; ++ j)
blg[j] = i ; sort(t + 1, t + n + 1) ;
w = unique(t + 1, t + n + 1) - t - 1 ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = lower_bound(t + 1, t + w + 1, g[i]) - t ;
// for (int i = 1 ; i <= n ; ++ i) cout << base[i] << '\n' ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i ;
sort(q + 1, q + m + 1, comp), l = 1, r = 0, lb = 0 ;
// cout << 233 << endl ;
// for (int i = 1 ; i <= n ; ++ i) cout << blg[i] << " " ;
for (int i = 1 ; i <= m ; ++ i){
if (blg[q[i].l] == blg[q[i].r]){
// cout << q[i].l << " " << q[i].r << endl ;
ans[q[i].id] = brute_force(q[i].l, q[i].r) ;
continue ;
}
if (blg[q[i].l] ^ lb){
while (r > R[blg[q[i].l]]) del(r --) ;
while (l < R[blg[q[i].l]] + 1) del(l ++) ;
res = 0 ; lb = blg[q[i].l] ;
}
int ul = l ; LL anss = res ;
while (r < q[i].r) add(++ r, res) ;
anss = res ; while (ul > q[i].l) add(-- ul, anss) ;
while (ul < l) del(ul ++) ; ans[q[i].id] = anss ;
}
for (int i = 1 ; i <= m ; ++ i)
printf("%lld\n", ans[i]) ; return 0 ;
}

LG 5906 回滚莫队

给定一个序列,多次询问一段区间 $[l,r]$,求区间中相同的数的最远间隔距离

序列中两个元素的间隔距离指的是两个元素下标差的绝对值

$1\leq n,m\leq 2\cdot 10^5$

本质上第一次见这题是某次校内胡策 戳我。之后发现原来是 codechef 上的题,然后就自己出了数据放到了谷上……然而数据十分的水……虽然我觉得我是精心构造了…233

然后这题其实是道好题…原因就是上一道题是不完全版的回滚莫队:上一道题的左端点 add 和右端 add 可以一样,因为第二层信息 buc 可以差分,即如果现减成 $-1$ 后来是可以加回来的;但是这道题的话,如果记录上一个和下一个相同的数字的位置会有很麻烦的边界,大部分做法都是赋值为 $0$ 或 $n$ ,但这样就会丢失信息,也就是左端点的 add 和右端点的 add 要分开处理。

所以如果铁憨憨地拿头写就会由很多边界,所以比较好的处理方式:

询问分块处理

大概就是每个块清零一次,直接让两个指针回归。这样做不容易错,但复杂度是满的 $\frac{n^2}{\sqrt m}$ (因为每个块都是 $\Theta(n)$ 的清零)。所以大概可以改下块大小来微调?但其实这题我出的所有 $n,m$ 差不超过 $5$ …233

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
using namespace std ;

const int N = 200010 ;
const int M = 200010 ;

struct qs{
int l, r, id ;
}q[M] ;
int len ;
int res ;
int buc[N] ;
int blg[N] ;
int ans[N] ;
int b, bnum ;
int L[N], R[N] ;
int n, m, x, y ;
int val[N], base[N] ;
int pre[N], tmp[N], suf[N] ;

inline bool comp(const qs &a, const qs &b){
return blg[a.l] == blg[b.l] ? a.r < b.r : blg[a.l] < blg[b.l] ;
}
inline int qr(){
int k = 0 ;
char c = getchar() ; while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k ;
}
inline int Min(const int &a, const int &b){ return a < b ? a : b ; }
inline int Max(const int &a, const int &b){ return a > b ? a : b ; }
inline int brute_force(int l, int r){
int ret = 0 ;
for (int i = l ; i <= r ; ++ i) tmp[base[i]] = n ;
for (int i = l ; i <= r ; ++ i)
tmp[base[i]] = Min(tmp[base[i]], i), ret = Max(ret, i - tmp[base[i]]) ;
return ret ;
}
inline void add(const int &p){
suf[base[p]] = Max(suf[base[p]], p) ;
pre[base[p]] = Min(pre[base[p]], p) ;
res = Max(res, suf[base[p]] - pre[base[p]]) ;
}
int solve(int s, int bnum){
int i = s, L = Min(n, bnum * b) ;
int l = L + 1, r = L ; res = 0 ;
fill(pre + 1, pre + len + 1, n) ;
fill(suf + 1, suf + len + 1, 0) ;
for( ; blg[q[i].l] == bnum ; ++ i ){
if (blg[q[i].l] == blg[q[i].r]){
ans[q[i].id] = brute_force(q[i].l, q[i].r) ;
continue ;
}
int anss = 0 ;
while (r < q[i].r) add(++ r) ;
for (int j = q[i].l ; j <= l ; ++ j) tmp[base[j]] = n ;
for (int j = q[i].l ; j <= l ; ++ j){
tmp[base[j]] = Min(tmp[base[j]], j) ;
anss = max(anss, Max(j - tmp[base[j]], suf[base[j]] - j)) ;
}
ans[q[i].id] = max(anss, res) ;// cout << i << endl ;
}
return i ;
}
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), val[i] = base[i] ;
sort(val + 1, val + n + 1) ;
cin >> m ; b = n / sqrt(m) ;
len = unique(val + 1, val + n + 1) - val - 1 ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = lower_bound(val + 1, val + len + 1, base[i]) - val ;
for (int i = 1 ; i <= m ; ++ i)
q[i].l = qr(), q[i].r = qr(), q[i].id = i ;
for (int i = 1 ; i <= n ; ++ i) blg[i] = (i - 1) / b + 1 ;
sort(q + 1, q + m + 1, comp) ; int L = 1 ;
for (int i = 1 ; i <= blg[n] ; ++ i) {
L = solve(L, i) ; if (L > m) break ;
}
for (int i = 1 ; i <= m ; ++ i) printf("%d\n", ans[i]) ; return 0 ;
}

把所有函数展开

没写过,因为个人认为会搞乱码风。


瞎写

于是个人最初的写法是这样的,十分吊诡:

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

const int N = 400100 ;
const int M = 400100 ;

int res ;
int len ;
int n, m ;
int buf[N] ;
int tmp[N] ;
int blg[N] ;
int ans[M] ;
int tbuc[N] ;
int bucp[N] ;
int bucs[N] ;
int base[N] ;
int b, bnum ;
struct qs{
int id ;
int l, r ;
}q[M] ;

bool comp(qs a, qs b){
if (blg[a.l] ^ blg[b.l])
return blg[a.l] < blg[b.l] ;
return a.r < b.r ;
}
int brute_force(int l, int r){
int ret = 0 ;
for (int i = l ; i <= r ; ++ i){
if (!buf[base[i]]) buf[base[i]] = i ;
else{
ret = max(ret, i - buf[base[i]]) ;
buf[base[i]] = min(i, buf[base[i]]) ;
}
}
for (int i = l ; i <= r ; ++ i)
if (buf[base[i]]) buf[base[i]] = 0 ;
return ret ;
}
void del(int x){
bucp[base[x]] = N ;
bucs[base[x]] = 0 ;
}
void add(int x, int &val){
bucs[base[x]] = max(x, bucs[base[x]]) ;
bucp[base[x]] = min(x, bucp[base[x]]) ;
val = max(val, bucs[base[x]] - bucp[base[x]]) ;
}
int main(){
cin >> n ;
int l = 1, r = 0, k = -1 ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), tmp[i] = base[i] ;
sort(tmp + 1, tmp + n + 1) ;
len = unique(tmp + 1, tmp + n + 1) - tmp - 1 ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = lower_bound(tmp + 1, tmp + len + 1, base[i]) - tmp ;
cin >> m ; b = n / sqrt(m) ;
for (int i = 1 ; i <= n ; ++ i) blg[i] = i / b ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i ;
sort(q + 1, q + m + 1, comp) ;
for (int i = 1 ; i <= n ; ++ i) bucs[i] = 0, bucp[i] = N ;
for (int i = 1 ; i <= m ; ++ i){
if (blg[q[i].l] == blg[q[i].r])
ans[q[i].id] = brute_force(q[i].l, q[i].r) ;
else{
if (blg[q[i].l] > k){
while (blg[r] <= blg[q[i].l]) del(r ++) ;
while (blg[r] > blg[q[i].l]) del(r --) ;
while (blg[l] <= blg[q[i].l]) del(l ++) ;
add(++ r, res) ; res = 0 ; k = blg[q[i].l] ;
}
int t, fl = l, ress = 0 ;
while (r < q[i].r) add(++ r, res) ;
for (int j = q[i].l ; j <= l ; ++ j) tbuc[base[j]] = N ;
for (int j = q[i].l ; j <= l ; ++ j){
t = base[j] ;
tbuc[t] = min(j, tbuc[t]) ;
ress = max(ress, max(j - tbuc[t], bucs[t] - j)) ;
}
ans[q[i].id] = max(ress, res) ;
}
}
for (int i = 1 ; i <= m ; ++ i) printf("%d\n", ans[i]) ;
return 0 ;
}

边界很烦人…很烦人…当然个人实力菜占主要原因…

不过最后好歹也算是调出来了,QAQ