回滚莫队

今天学习了回滚莫队,忍不住手痒写一下学习笔记。(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 } 
相关文章