回滚莫队学习笔记

栏目: IT技术 · 发布时间: 4年前

内容简介：今天学习了回滚莫队，忍不住手痒写一下学习笔记。（bushi回滚莫队其实十分的简单易懂。为什么需要回滚莫队呢？

回滚莫队

今天学习了回滚莫队，忍不住手痒写一下学习笔记。（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 ₁ ...X _N

输出格式

输出Q行，第i行( 1 ≤ i ≤ Q)一个整数，表示第i次询问的最大重要度

样例

输入样例

输出样例

数据范围与提示

1 ≤ N ≤ 1 0 ⁵ ,

  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 }

以上所述就是小编给大家介绍的《回滚莫队学习笔记》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对码农网的支持！

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

程序员代码面试指南：IT名企算法与数据结构题目最优解（第2版）

左程云 / 电子工业出版社 / 109.00元

《程序员代码面试指南：IT名企算法与数据结构题目最优解（第2版）》是一本程序员代码面试"神书”！书中对IT名企代码面试各类题目的最优解进行了总结，并提供了相关代码实现。针对当前程序员面试缺乏权威题目汇总这一痛点，本书选取将近300道真实出现过的经典代码面试题，帮助广大程序员的面试准备做到接近万无一失。"刷”完本书后，你就是"题王”！《程序员代码面试指南：IT名企算法与数据结构题目最优解（第2版）》......一起来看看《程序员代码面试指南：IT名企算法与数据结构题目最优解（第2版）》这本书的介绍吧!

码农工具