回滚莫队学习笔记

微信扫一扫,分享到朋友圈

回滚莫队学习笔记

回滚莫队

今天学习了回滚莫队,忍不住手痒写一下学习笔记。(bushi

回滚莫队其实十分的简单易懂。

为什么需要回滚莫队呢?

普通的莫队可以O(1)维护从(L , R)转移到(L ± 1 , R) , (L , R ± 1),但是,有一些维护值 扩展容易收缩难,或者 收缩容易扩展难。

比如,最大值的维护就是扩展容易收缩难。举个例子:我们要从(L , R)转移到(L+1 , R),那么a L
就不在区间中了,可是我们很难判断a L
是否为(L , R)中的最大值,如果是,且唯一,则(L+1 , R)的最大值就不再是a L
,因为a L
已经被移出区间,我们也不知道(L+1 , R)的最大值究竟是多少。这样,就无法转移了。

此时,
回滚莫队

闪亮登场!

回滚莫队的思想

只在左端点在同一分块内时才转移。当左端点在新的分块内时,初始化所有。

因为左端点在同一分块内的是按右端点排序,所以右端点肯定是单向扩展或收缩的,像普通莫队一样扩展即可。

左端点是乱序的,所以每次都从当前分块的右边界开始往左边扩展到左端点,这样就只会扩展而不会面临收缩的局面(如果是收缩容易扩展难就从左边界开始收缩)。

时间复杂度依然是O(n√n)。

回滚莫队的具体实现(扩展容易收缩难为例)

1. 对原序列进行分块,并对询问按照如下的方式排序:以左端点所在的块升序为第一关键字,以右端点升序为第二关键字。( 注意:我们不能使用奇偶优化

2. 遍历所有分块。

3. 我们先将莫队当前分块区间左端点初始化为分块的右边界+1,右端点初始化为分块块的右边界,这是一个空区间。

4.
左右端点在同一个分块中的询问

,我们直接暴力遍历即可。然后再遍历一次修改回原样。

5.
左右端点不在同一个分块中的询问

,一直扩展莫队区间右端点直到区间右端点与询问右端点重合。区间左端点每次都从当前分块的右边界开始往左边扩展到左端点。然后再把区间左端点扫回分块右边界+1,把所有数据修改回原样。(回滚)

6.所有左端点在当前分块内的询问遍历结束后,清空所有数据。(就是把区间右端点扫回分块右边界)(回滚)

下面,我们来看一道板子题:

洛咕 AT1219 历史研究

题目描述

IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。

日记中记录了连续N天发生的时间,大约每天发生一件。






1





i




N)发生的事件的种类用一个整数X i
表示,X i
越大,事件的规模就越大。

JOI教授决定用如下的方法分析这些日记:

1.选择日记中连续的一些天作为分析的时间段

2.事件种类t的重要度为t*(这段时间内重要度为t的事件数)

3.计算出所有事件种类的重要度,输出其中的最大值

现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

















输入格式

第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。 接下来一行N个空格分隔的整数

X 1
…X N

输出格式

输出Q行,第i行(





1





i




Q)一个整数,表示第i次询问的最大重要度
















样例

输入样例

输出样例

数据范围与提示

1





N





1

0 5













1 //回滚莫队
2 //洛咕AT1219 历史研究
3
4 #include <iostream>
5 #include <algorithm>
6 #include <cstdio>
7 #include <cstring>
8 #include <cmath>
9 #define ll long long
10 #define inf0x3f3f3f3f
11 using namespace std;
12 int read(){
13     int ret=0,ttt=1;
14     char ch=getchar();
15     while(ch<'0' || ch>'9'){
16         if(ch=='-'){
17             ttt=-1;
18         }ch=getchar();
19     }while(ch>='0' && ch<='9'){
20         ret=(ret<<1)+(ret<<3)+(ch^48);
21         ch=getchar();
22     }return ret*ttt;
23 }
24 struct dat{
25     int l,r,p; //询问左端点、右端点、询问编号(方便在排序后按输入顺序输出答案)
26 };
27 int n,m,sq;
28 int a[100005],pos[100005],num[100005],v[100005],b[100005]; //a 种类, b 存原来的a, v 离散值, pos[i] i属于的分块号, num 种类出现次数
29 ll ans[100005];
30 dat no[100005]; //询问
31 bool cmp(dat u, dat v){
32     if(pos[u.l]==pos[v.l]){
33         return u.r<v.r;
34     }return u.l<v.l;
35 }
36 int tt;
37 void in(){ //离散化(莫队不需要,是由于题目原因)
38     sort(a+1,a+n+1);
39     tt=n;
40     tt=unique(a+1,a+tt+1)-(a+1);
41     for(int i=1; i<=n; i++){
42         v[i]=lower_bound(a+1,a+tt+1,b[i])-a;
43     }
44 }
45 int main(){
46     n=read(),m=read();
47     sq=int(sqrt(n));
48     int sum=0,cnt=0;
49     for(int i=1; i<=n; i++){
50         a[i]=read();
51         b[i]=a[i]; //离散化
52         if(i>sum){
53             sum+=sq;
54             cnt++;
55         }pos[i]=cnt;
56     }in();
57     for(int i=1; i<=m; i++){
58         no[i].l=read(),no[i].r=read();
59         no[i].p=i;
60     }sort(no+1,no+m+1,cmp);
61     int p=1;
62     for(int k=1; k<=n; k+=sq){ //遍历所有块
63         int you=min(k+sq-1,n),zuo=you+1; //莫队区间左右端点
64         ll now=0,tmp=0;
65         for(int j=p; j<=m; j++){
66             int l=no[j].l,r=no[j].r;
67             if(l>min(k+sq-1,n)){
68                 p=j;
69                 break;
70             }if(j==m){
71                 p=m+1;
72             }if(pos[l]==pos[r]){ //特判:询问左右端点在同一块中
73                 for(int i=l; i<=r; i++){ //暴力扫
74                     num[v[i]]++;
75                     now=max(now,1ll*b[i]*num[v[i]]);
76                 }ans[no[j].p]=max(ans[no[j].p],now);
77                 now=tmp;
78                 for(int i=l; i<=r; i++){
79                     num[v[i]]--; //回滚
80                 }continue;
81             }while(you<r){ //扩展右端点
82                 you++;
83                 num[v[you]]++;
84                 now=max(now,1ll*b[you]*num[v[you]]);
85             }tmp=now; //tmp记录此时的now值
86             while(zuo>l){ //扩展左端点
87                 zuo--;
88                 num[v[zuo]]++;
89                 now=max(now,1ll*b[zuo]*num[v[zuo]]);
90             }ans[no[j].p]=max(ans[no[j].p],now);
91             now=tmp; //回滚now值
92             while(zuo<k+sq){ //回滚左端点
93                 num[v[zuo]]--;
94                 zuo++;
95             }
96         }while(you>k+sq-1){ //整个块遍历结束,回滚右端点
97             num[v[you]]--;
98             you--;
99         }
100     }for(int i=1; i<=m; i++){
101         printf("%lld\n",ans[i]);
102     }
103     return 0;
104 }

微信扫一扫,分享到朋友圈

回滚莫队学习笔记

ThinkPHP6 核心分析之应用程序初始化

上一篇

消息称:字节跳动同意剥离TIKTOK美国业务

下一篇

你也可能喜欢

回滚莫队学习笔记

长按储存图像,分享给朋友