日志

回滚莫队学习笔记

 来源    2020-08-01    0  

回滚莫队

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

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

为什么需要回滚莫队呢?

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

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

此时,回滚莫队闪亮登场!

回滚莫队的思想

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

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

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

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

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

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

2. 遍历所有分块。

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

4. 左右端点在同一个分块中的询问,我们直接暴力遍历即可。然后再遍历一次修改回原样。

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

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

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

JSOI 2014 历史研究

题目描述

IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间,大约每天发生一件。
事件有种类之分。第i天(1iN)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。
JOI教授决定用如下的方法分析这些日记:
1.选择日记中连续的一些天作为分析的时间段
2.事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3.计算出所有事件种类的重要度,输出其中的最大值
现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

输入格式

第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。 接下来一行N个空格分隔的整数X1...XNXi表示第i天发生的事件的种类 接下来Q行,第i行(1iQ)有两个空格分隔整数AiBi,表示第i次询问的区间为[Ai,Bi]。

输出格式

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

样例

输入样例

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

输出样例

9
8
8
16
16

数据范围与提示

1N1051Q1051Xi109 (1iN)

这题就是模版题,只是要注意两点,一是离散化,二是开long long

不多说了,上代码 (可以当模板用,自认为码风还是比较易懂的

//回滚莫队 
//JSOI2014 历史研究 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define ll long long
#define inf0x3f3f3f3f
using namespace std; 
int read(){
    int ret=0,ttt=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-'){
            ttt=-1;
        }ch=getchar();
    }while(ch>='0' && ch<='9'){
        ret=(ret<<1)+(ret<<3)+(ch^48);
        ch=getchar();
    }return ret*ttt;
}
struct dat{
    int l,r,p; //询问左端点、右端点、询问编号(方便在排序后按输入顺序输出答案) 
};
int n,m,sq;
int a[100005],pos[100005],num[100005],v[100005],b[100005]; //a 种类, b 存原来的a, v 离散值, pos[i] i属于的分块号, num 种类出现次数 
ll ans[100005];
dat no[100005]; //询问 
bool cmp(dat u, dat v){
    if(pos[u.l]==pos[v.l]){
        return u.r<v.r;
    }return u.l<v.l;
}
int tt;
void in(){ //离散化(莫队不需要,是由于题目原因) 
    sort(a+1,a+n+1);
    tt=n;
    tt=unique(a+1,a+tt+1)-(a+1);
    for(int i=1; i<=n; i++){
        v[i]=lower_bound(a+1,a+tt+1,b[i])-a;
    }
}
int main(){
    n=read(),m=read();
    sq=int(sqrt(n));
    int sum=0,cnt=0;
    for(int i=1; i<=n; i++){
        a[i]=read();
        b[i]=a[i]; //离散化 
        if(i>sum){
            sum+=sq;
            cnt++;
        }pos[i]=cnt;
    }in();
    for(int i=1; i<=m; i++){
        no[i].l=read(),no[i].r=read();
        no[i].p=i;
    }sort(no+1,no+m+1,cmp);
    int p=1;
    for(int k=1; k<=n; k+=sq){ //遍历所有块 
        int you=min(k+sq-1,n),zuo=you+1; //莫队区间左右端点 
        ll now=0,tmp=0;
        for(int j=p; j<=m; j++){
            int l=no[j].l,r=no[j].r;
            if(l>min(k+sq-1,n)){
                p=j;
                break;
            }if(j==m){
                p=m+1;
            }if(pos[l]==pos[r]){ //特判:询问左右端点在同一块中 
                for(int i=l; i<=r; i++){ //暴力扫 
                    num[v[i]]++;
                    now=max(now,1ll*b[i]*num[v[i]]);
                }ans[no[j].p]=max(ans[no[j].p],now);
                now=tmp;
                for(int i=l; i<=r; i++){
                    num[v[i]]--; //回滚 
                }continue;
            }while(you<r){ //扩展右端点 
                you++;
                num[v[you]]++;
                now=max(now,1ll*b[you]*num[v[you]]);
            }tmp=now; //tmp记录此时的now值 
            while(zuo>l){ //扩展左端点 
                zuo--;
                num[v[zuo]]++;
                now=max(now,1ll*b[zuo]*num[v[zuo]]);
            }ans[no[j].p]=max(ans[no[j].p],now);
            now=tmp; //回滚now值 
            while(zuo<k+sq){ //回滚左端点 
                num[v[zuo]]--;
                zuo++;
            }
        }while(you>k+sq-1){ //整个块遍历结束,回滚右端点 
            num[v[you]]--;
            you--;
        }
    }for(int i=1; i<=m; i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

分块&&莫队学习笔记
日志坑太大了,一时甚至填不起来(现在只填到分块) 分块和莫队都是非常好的暴力算法, 能够让人在面对一些要求维护特殊序列的题时,可以拿到暴力高分甚至AC 甚至还多次出现在各地省选中,学了不亏的好东西 (但是 ...
1
LOJ#6504. 「雅礼集训 2018 Day5」Convex(回滚莫队)
日志题面 传送门 题解 因为并不强制在线,我们可以考虑莫队 然而莫队的时候有个问题,删除很简单,除去它和前驱后继的贡献即可.但是插入的话却要找到前驱后继再插入,非常麻烦 那么我们把它变成只删除的回滚莫队就 ...
[BZOJ4241]历史研究(回滚莫队)
日志将整个序列分成$\sqrt{n}$块,所有询问按左端点所在块为第一关键字,右端点所在块为第二关键字排序. 当右端点增加或左端点减小时,更新桶与答案.但是左端点增加时需要删除,这时就必须用堆等数据结构维 ...
BZOJ4241:历史研究(回滚莫队)
日志题意:给定N个数字,Q次询问,询问这个区间的最大加权众数是多少. 加权众数是指出现次数*数字大小.N,Q<1e5. 思路:不难发现可以N*sqrtN*logN的思路做,但是应该过不了. 这个Ns ...
Codeforces 620F Xors on Segments 回滚莫队 + 字典树 || 离心询问分治 + 可持久化字典树
日志Xors on Segments 转换一下变成询问区间选两个数异或的最大值, 要注意的是一个数作为左端点要-1, 所以在回滚莫队的时候用两棵字典树维护. 这个题居然n ^ 2 也能过...  其实用分 ...
HihoCoder 1629 Graph (2017 ACM-ICPC 北京区域赛 C题,回滚莫队 + 启发式合并 + 可撤销并查集)
日志题目链接  2017 ACM-ICPC Beijing Regional Contest Problem C 题意  给定一个$n$个点$m$条边的无向图.现在有$q$个询问,每次询问格式为$[l, ...
BZOJ4241历史研究——回滚莫队
日志题目描述 IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记.JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件. 日记中记录了连 ...
Bzoj4241: 历史研究——回滚莫队
日志题面 Bzoj 解析 今天Doggu讲了根号类算法,这道题使用的就是其中之一的回滚莫队. 这道题显然支持离线操作,询问区间,立即联想到莫队,对于区间扩大的信息更新是很容易的,但要区间缩小,信息的更新就 ...
1
树上莫队学习笔记
日志树上莫队学习笔记 前言 今天(19.7.12)A组第一题是一道树上莫队裸题 就学一下咯 参考 莫队算法--从入门到黑题 胡小兔的良心莫队教程:莫队.带修改莫队.树上莫队 正文 前置知识 欧拉序 这里的 ...
1
AT1219 歴史の研究(回滚莫队)
日志题目描述 IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记.JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件. 日记中记录了连 ...
1
回文树/回文自动机(PAM)学习笔记
日志回文树(也就是回文自动机)实际上是奇偶两棵树,每一个节点代表一个本质不同的回文子串(一棵树上的串长度全部是奇数,另一棵全部是偶数),原串中每一个本质不同的回文子串都在树上出现一次且仅一次. 一个节点的 ...
学习笔记1-回顾树状数组与莫队思路
日志今天回顾了一下树状数组的有关内容. 可以说是今天才看懂树状数组的意思吧..对之前的理解毫无印象.. 现在这里马克一下 树状数组: 树状数组是用于存储数据的一种特殊的数据结构.具体的形状如下图: a数组 ...
1
BZOJ 2038: [2009国家集训队]小Z的袜子(hose)莫队算法裸题&&学习笔记
日志2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 9894  Solved: 4561[Subm ...
1
BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]学习笔记
日志题意: 询问区间中不同颜色的个数,单点修改颜色 发现以前写的学习笔记没法看,于是重写一下(不就是会用latex了嘛) 额外维护一个当前修改操作执行到的时间 如果要进行某个查询操作,修改操作的时间必须移 ...
1
BZOJ 2038: [2009国家集训队]小Z的袜子(hose) [莫队算法]学习笔记
日志2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 7687  Solved: 3516[Subm ...
1
[学习笔记]树上莫队
日志远古博客:莫队算法——暴力出奇迹 https://blog.csdn.net/u012061345/article/details/54093879 树上莫队也就一句话: 把树上路径用欧拉序(入栈出栈 ...
1
「莫队」学习笔记
日志莫队用来离线解决区间询问问题. 一.不带修莫队 考虑利用分块的方法对所有询问的区间按照一定的顺序来回答,而不是完全按照输入顺序在线回答,从而使历史信息得到充分利用.这就是莫队相较于暴力要优的地方. 对 ...
2
学习笔记 莫队算法
日志零. 这是一篇特别草率的学习笔记. 一.关于莫队 一种离线的关于区间操作的算法. 一般莫队会和以下知识点一起使用: 1.分块思想. 2.离散化. 3.树链剖分/倍增,用于应付树上的(然而本蒟蒻写这篇博 ...
2
Android学习笔记_9_SQLiteOpenHelper对象之数据库增删改查以及事务回滚操作
日志一.SQLite数据库: 在Android平台上,集成了一个嵌入式关系型数据库—SQLite,SQLite3支持 NULL.INTEGER.REAL(浮点数字).TEXT(字符串文本)和BLOB(二进 ...
1
springmvc学习笔记--json--返回json的日期格式问题
日志(一)输出json数据 springmvc中使用jackson-mapper-asl即可进行json输出,在配置上有几点: 1.使用mvc:annotation-driven 2.在依赖管理中添加ja ...
1