首页 > 其他分享 >回滚莫队

回滚莫队

时间：2024-08-18 20:15:18浏览次数：13  
标签：回滚 int res long 端点 using 莫队

当普通莫队做一些删除操作或增加操作非常困难时，回滚莫队便腾空出现，解救苍生

针对困难的操作，分为两种回滚莫队，一个是不删除莫队，一个是不增加莫队。

核心思路都是一样的 : 既然只能实现一种操作，那么就只用一种操作，剩下的交给回滚解决。

什么是回滚

回滚（Rollback）指的是程序或数据处理错误，将程序或数据恢复到上一次正确状态的行为。回滚包括程序回滚和数据回滚等类型。 —— 来自百度百科

不删除莫队

既然删除非常困难，那么就干脆删除不就好啦

例题 : 歴史の研究

发现这道题的增加操作可以\(O(1)\)，只需要与当前最大值取\(\max\)即可。

但是删除操作难以\(O(1)\)维护，当把最大值删除后，无法立刻得知次大值。

于是就可以考虑回滚莫队或者其他做法了

典型的不删除莫队，大致的流程是这样的

  1. 输入，对序列分块，将询问按照左端点所属块的编号升序为第一关键字，右端点升序为第二关键字排序
  2. 处理询问，枚举左端点所属的块，将莫队的左端点指针\(l\)指向当前块右端点+1的位置，右端点指针\(r\)指向当前块的右端点。
    1. 如果询问的左右端点所属块相同，暴力即可
    2. 如果不同，拓展右指针，记录当前状态，再拓展左指针，记录答案
    3. 将左指针所造成的改动还原，注意不是删除操作，只是还原为拓展前所记录的状态

本来想画一个图，但由于条件不允许，于是便咕了

看看代码,应该比较好理解

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10,M = 350;
struct node{int l,r,id;}q[N];
int n,m,L[M],R[M],cnt[N],pos[N],len,a[N],c[N];
ll ans[N],res;
vector<int> num;
inline void solve(){
    cin>>n>>m;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 1;i <= m; ++i) cin>>q[i].l>>q[i].r,q[i].id = i;

    for(int i = 1;i <= n; ++i) num.emplace_back(a[i]);
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    for(int i = 1;i <= n; ++i)
        a[i] = lower_bound(num.begin(),num.end(),a[i]) - num.begin() + 1;
    int V = num.size();

    len = sqrt(n);
    for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i*len;
    if(R[len] < n) len++,L[len] = R[len - 1] + 1,R[len] = n;
    for(int i = 1;i <= len; ++i) for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
    sort(q+1,q+1+m,[](node x,node y){return pos[x.l] == pos[y.l]?x.r<y.r:x.l<y.l;});
    //以上是输入，初始化，注意排序函数

    auto BF = [&](int l,int r) -> ll{
        ll res = 0;
        for(int i = l;i <= r; ++i) c[a[i]] ++;
        for(int i = l;i <= r; ++i) res = max(res,1ll*c[a[i]]*num[a[i]-1]);
        for(int i = l;i <= r; ++i) c[a[i]] --;
        return res;
    };//暴力代码，应该挺好懂得
    
    auto add = [&](int x) -> void{
        cnt[a[x]]++;
        res = max(res,1ll*cnt[a[x]]*num[a[x]-1]);
    };//O(1)的添加操作
    

    for(int i = 1,l,r,now = 1;i <= len; ++i){
        for(int j = 1;j <= V; ++j) cnt[j] = 0;
        r = R[i];res = 0;
        while(pos[q[now].l] == i){
            l = R[i] + 1;
            if(q[now].r - q[now].l < len){//如果查询在同一块内，直接暴力
                ans[q[now].id] = BF(q[now].l,q[now].r);
                now++;
                continue;
            }
            while(r < q[now].r) add(++r);//拓展右指针
            ll tmp = res;//记录拓展前的状态
            while(l > q[now].l) add(--l);//拓展左指针
            ans[q[now].id] = res;//记录答案
            //还原
            res = tmp;
            while(l <= R[i]) --cnt[a[l++]];
            now++;
        }
    }
    
    for(int i = 1;i <= m; ++i) cout<<ans[i]<<'\n';

}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve(); 
}

例题 : 【模板】回滚莫队&不删除莫队

模板题，随便打。

但是我的记录状态的方式比较抽象。

简单说一下思路，就是记录一个值出现位置的左右端点，然后增加的时候取差即可。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10,M = 500;
struct node{int l,r,id;}q[N];
int n,m,L[M],R[M],pos[N],len,a[N],c1[N],c2[N],lt[N],rt[N],c[N],ans[N],res;
vector<int> num;
inline void solve(){
    memset(c1,0x3f,sizeof c1);

    cin>>n;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    cin>>m;
    for(int i = 1;i <= m; ++i) cin>>q[i].l>>q[i].r,q[i].id = i;

    for(int i = 1;i <= n; ++i) num.emplace_back(a[i]);
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    for(int i = 1;i <= n; ++i)
        a[i] = lower_bound(num.begin(),num.end(),a[i]) - num.begin() + 1;
    int V = num.size();

    len = sqrt(n);
    for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i*len;
    if(R[len] < n) len++,L[len] = R[len - 1] + 1,R[len] = n;
    for(int i = 1;i <= len; ++i) for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
    sort(q+1,q+1+m,[](node x,node y){return pos[x.l] == pos[y.l]?x.r<y.r:x.l<y.l;});

    
    auto BF = [&](int l,int r) -> int{
        int res = 0;
        for(int i = l;i <= r; ++i) 
            c1[a[i]] = min(c1[a[i]],i),c2[a[i]] = max(c2[a[i]],i);
        for(int i = l;i <= r; ++i) res = max(res,c2[a[i]] - c1[a[i]]);
        for(int i = l;i <= r; ++i) c1[a[i]] = 0x3f3f3f3f,c2[a[i]] = 0;
        return res;
    };
    
    auto add = [&](int x) -> void{
        rt[a[x]] = max(rt[a[x]],x);
        lt[a[x]] = min(lt[a[x]],x);
        res = max(res,rt[a[x]] - lt[a[x]]);
    };
    
    for(int i = 1,l,r,now = 1;i <= len; ++i){
        for(int j = 1;j <= V; ++j) lt[j] = 0x3f3f3f3f,rt[j] = 0;
        r = R[i];res = 0;
        while(pos[q[now].l] == i){
            l = R[i] + 1;
            if(q[now].r - q[now].l < len){
                ans[q[now].id] = BF(q[now].l,q[now].r);
                now++;
                continue;
            }
            while(r < q[now].r) add(++r);
            int tmp = res;
            for(int j = l;j >= q[now].l;--j) c[a[j]] = lt[a[j]];
            while(l > q[now].l) add(--l);
            ans[q[now].id] = res;
            res = tmp;
            while(l <= R[i]) lt[a[l]] = c[a[l]],l++;
            now++;
        }
    }
    
    for(int i = 1;i <= m; ++i) cout<<ans[i]<<'\n';

}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve(); 
}
  1. BZOJ4358 permu

本来说要打这题但因为电脑死机了好不容易敲完的博客没了，于是水过去了，这篇博客是第二遍敲得

md，我要回hs

一句话题解，可撤销并查集+不删除莫队。

等模拟赛调完再打

不增加莫队

大致思路和不删除莫队一样，流程有所改变，将流程中改变的地方用粗体标注

  1. 输入，对序列分块，将询问按照左端点所属块的编号升序为第一关键字，右端点降序为第二关键字排序
  2. 处理询问，枚举左端点所属的块，将莫队的左端点指针\(l\)指向当前块左端点的位置，右端点指针\(r\)指向n。
    1. 如果询问的左右端点所属块相同，暴力即可
    2. 如果不同，拓展右指针，记录当前状态，再拓展左指针，记录答案
    3. 将左指针所造成的改动还原，注意不是删除操作，只是还原为拓展前所记录的状态

例题 : Rmq Problem / mex

删除只需要取\(\min\)，而加入却要\(O(V)\)更改

于是就是不删除莫队了，比较简单。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10,M = 500;
struct node{int l,r,id;}q[N];
int n,m,L[M],R[M],pos[N],len,a[N],ans[N],res,cnt[N],c[N];
vector<int> num;
inline void solve(){
    int V = 0;
    cin>>n>>m;
    for(int i = 1;i <= n; ++i) cin>>a[i],V = max(V,a[i]);
    for(int i = 1;i <= m; ++i) cin>>q[i].l>>q[i].r,q[i].id = i;
    V++;

    len = sqrt(n);
    for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i*len;
    if(R[len] < n) len++,L[len] = R[len - 1] + 1,R[len] = n;
    for(int i = 1;i <= len; ++i) for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
    sort(q+1,q+1+m,[](node x,node y){return pos[x.l] == pos[y.l]?x.r>y.r:x.l<y.l;});
    
    auto BF = [&](int l,int r) -> int{
        int res = 0;
        for(int i = l;i <= r; ++i) c[a[i]]++;
        for(int i = 0;i <= V; ++i) if(!c[i]){res = i;break;}
        for(int i = l;i <= r; ++i) c[a[i]]--;
        return res;
    };

    auto del = [&](int x) -> void{
        cnt[a[x]]--;
        if(!cnt[a[x]]) res = min(res,a[x]);
    };


    for(int i = 1,now = 1,l,r;i <= len; ++i){
        for(int j = 0;j <= V; ++j) cnt[j] = 0;
        for(int j = L[i];j <= q[now].r; ++j) cnt[a[j]]++;
        for(int j = 0;j <= V; ++j) if(!cnt[j]){res = j;break;}
        r = q[now].r;
        while(pos[q[now].l] == i){
            l = L[i];
            if(q[now].r - q[now].l <= len){
                ans[q[now].id] = BF(q[now].l,q[now].r);
                now++;
                continue;
            }
            while(r > q[now].r) del(r),r--;
            int tmp = res;
            while(l < q[now].l) del(l),l++;
            ans[q[now].id] = res;
            res = tmp;
            while(l > L[i]) l--,cnt[a[l]]++;
            now++;
        }
    }
        
    for(int i = 1;i <= m; ++i) cout<<ans[i]<<'\n';

}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve(); 
}

but，普通莫队真的不可做吗?

普通莫队的复杂度为\(O(q\sqrt{n}+qv)\)，但是\(qv\)较小才4e10，然后要是给这个除以一个\(w\)——

bitset优化！！！

bitset中有一个成员函数，为\(_Find_next(int prev)\)，作用为查询\(prev\)下一个为\(true\)的位置，返回下标。

然后就可以暴力跑了。时间复杂度\(O(n\sqrt{n}+\frac{qv}{w})\)，算出来大概是\(7e8\)的，然后因为常数小，跑不满，再加上一堆玄学优化，轻微卡常，就过了……

跑得比上面那篇回滚莫队要快

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10,M = 500;
struct node{int l,r,id;}q[N];
int n,m,a[N],pos[N],L[M],R[M],len,ans[N],cnt[N];
bitset<N> have;
inline void solve(){
    cin>>n>>m;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 1;i <= m; ++i) cin>>q[i].l>>q[i].r,q[i].id = i;

    len = sqrt(n);
    for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i*len;
    if(R[len] < n) len++,L[len] = R[len - 1] + 1,R[len] = n;
    for(int i = 1;i <= len; ++i) for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
    sort(q+1,q+1+m,[](node x,node y){return pos[x.l] == pos[y.l]?(pos[x.l]&1?x.r<y.r:x.r>y.r):x.l<y.l;});
    
    have.set();

    int l = 1,r = 0,res = 0;
    auto add = [&](int x) -> void{
        cnt[a[x]]++;
        have.reset(a[x]);
        if(a[x] == res) res = have._Find_next(a[x]);
    };
    auto del = [&](int x) -> void{
        cnt[a[x]]--;
        if(!cnt[a[x]]) have.set(a[x]),res = min(res,a[x]);
    };
    for(int i = 1;i <= m; ++i){
        int left = q[i].l,right =q[i].r;
        while(l > left) l--,add(l);
        while(r < right) r++,add(r);
        while(l < left) del(l),l++;
        while(r > right) del(r),r--;
        ans[q[i].id] = res;
    }

    for(int i = 1;i <= m; ++i) cout<<ans[i]<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve(); 
}

时间复杂度证明 :

假设块长为\(b\)

如果左右端点在同一块中，为\(O(b)\)

反之，移动右端点的复杂度为\(O(n)\),由于左端点单次移动不会超过\(b\)，有\(\frac{n}{b}\)个块

所以时间复杂度为\(O(mb+\frac{n^2}{b})\)，块长取\(b=\frac{n}{\sqrt{m}}\)时最优，复杂度为\(O(n\sqrt{m})\)

没有太多的例题,主要是实在没时间打

标签：回滚,int,res,long,端点,using,莫队
From： https://www.cnblogs.com/hzoi-Cu/p/18366033

相关文章

  • 离线算法 莫队算法进阶
    前算是把之前的坑填一填吧。这篇文章主要包含带修莫队，二维莫队等莫队算法的进阶应用，观看前请确保您已经熟练掌握了基本的莫队算法，不会的可以戳这里。带修莫队众所周知，普通莫队是不支持修改的，因为我们为了得到更优的时间复杂度，需要将每次询问离线下来，打乱顺序。不过我们也......
  • 根号分治莫队
    莫队参考文章：莫队细讲——从零开始学莫队莫队算法——从入门到黑题oiwiki--普通莫队莫队简介莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经Codeforces的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析......
  • 数据结构 分块 & 莫队
    分块一种优化暴力的思想。通常是将原数据划分成适当块（一般为\(\sqrt{n}\)），对每块数据进行预处理，进而达到比暴力更优的时间复杂度。划分确定块长后，一般需要开两个数组存储每一块的右边界与原数据所属块序号，更加方便后续操作。intsq=sqrt(n);for(inti=1;i<=sq;i++)ed[i]=n/......
  • 回滚Git版本
    在Git的版本控制中，我们经常会遇到需要回滚到之前的某个Commit的情况。回滚操作可以帮助我们撤销之前的更改，返回到某个稳定的状态。下面，我将介绍几种常见的Git回滚方法，并提供实际操作步骤和示例代码。一、软回滚（SoftReset）软回滚会保留你的更改，但是会取消这些更改的提交。换句......
  • 【YashanDB数据库】大事务回滚导致其他操作无法执行，报错YAS-02016 no free undo block
    问题现象客户将一个100G的表的数据插入到另一个表中，使用insertintoselect插入数据。从第一天下午2点开始执行，到第二天上午10点，一直未执行完毕。由于需要实施下一步操作，客户kill重启了数据库，之后数据库一直回滚中，导致后续执行其他操作都报错YAS-02016nofreeundoblocks问题......
  • 莫队
    普通莫队把询问离线下来，按左端点分块，同一个块内按右端点排序。块长\(b=\dfrac{n}{\sqrtm}\)，注意特判\(m=0\)或让\(b=0\)的sb出题人，会RE。记录两个指针\(l,r\)，依次挪动到待查询区间。注意要先扩大再缩小，否则会出现正确性上的问题。trick：奇偶排序可以按照块序号的奇......
  • Contest7506 - 莫队 分块
    ContestA至少重复三次的数字莫队板子。B小明的习题集洛谷原题P1494[国家集训队]小Z的袜子。C棋子的颜色洛谷原题P1903[国家集训队]数颜色/维护队列。带修莫队：普通莫队是二维问题，现在加上一维时间轴，做法基本上同普通莫队。对询问\((l,r,t)\)排序时，第一关键......
  • MPT树是如何回滚的
    1,mpt树优于hash表，在区块连网络中，需要确认世界状态相同，hash表需要校验所有的hash2.使用序列表会导致插入过程麻烦，插入一条数据，整个链路都要更新MPT树是如何恢复的？（世界状态中的mpt树)mpt树的恢复与mpt树的更新是有关系的，在以太坊的生命周期中，世界状态的mpt树是根据更新的方式来......
  • 【数据结构】【模板】莫队
    莫队使用场景离线算法；区间询问不断修改。能用\(O(1)\)的时间复杂度从\([l,r]\)到\([l+1,r]\)或者\([l,r-1]\)。原理原问题可以转化为为建立一个坐标轴，对于一个询问\((l,r)\)，相当于点\((l,r)\)，从一个询问\((a,b)\)到\((c,d)\)，可以理解为点\((a,b)......
  • 莫队
    莫队假设\(n,m\)同阶，对于序列上的区间询问问题，如果得知\([l,r]\)的答案，可以在\(O(1)\)的时间推算出\([l-1,r],[l+1,r],[l,r-1],[l,r+1]\)的答案，那么我们就可以在\(O(n\sqrt{n})\)的时间求出所有询问的答案。普通莫队实现将所有的询问离线后以左......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99