数据结构 | 回滚莫队浅记

前置知识

之前写的普通莫队笔记,在这里当个前置知识,其实大约知道莫队大概就是把询问离线下来分块并排序之后用两个指针 \(l,r\) 来更新信息统计答案即可。

有时在区间转移的时候,有些删除或添加的操作无法实现,那么当只有一种操作不能实现的时候,就可以用莫队来解决这个问题,然而普通莫队是很难解决(或者说是不能解决)这个问题的,所以我们要对普通莫队进行改造,也就是回滚莫队。

本文出现所有代码缺省源使用V5.3.

「例题一」洛谷模板

原题链接:P5906 【模板】回滚莫队&不删除莫队

「例题一」题目简述

给定一个序列,多次询问一段区间 \([l,r]\),求区间中相同的数的最远间隔距离。

序列中两个元素的间隔距离指的是两个元素下标差的绝对值。

「例题一」思路简述

首先来说这个题有什么操作不能实现。显然增加是好实现的,只需要每次在增加时更新距离信息(记录第一次出现和最后一次出现)即可。但是删除操作不能这样实现,因为在删除的时候若要更新答案,需要知道次大值……肯定是不能这样维护的,所以我们要让 \(l\) 和 \(r\) 在移动的过程中尽量避免删除操作,也就是尽量让 \(l\) 向左端移动,\(r\) 向右端移动。

那么我们每次枚举块,把块内的询问解决的时候,每次把 \(l\) 拉回当前块的右端,然后保证 \(r\) 只向右端移动,\(l\) 不断根据询问反复横跳,对于在一个块内的询问暴力更新(复杂度 \(O(\sqrt{n})\),不过可能实际略大),否则跳两个指针更新答案。因为块的是 \(O(\sqrt{n})\) 的,所以对于每个询问,\(l\) 的移动是 \(O(\sqrt{n})\) 的,所以这样做的复杂度就是 \(O(n\sqrt{m}).\)

「例题一」Code


template<typename J>
I J Hmax(const J &x,const J &y) {
    Heriko x>y?x:y;
}

template<typename J>
I J Hmin(const J &x,const J &y) {
    Heriko x<y?x:y;
}

CI MXX(2e5+1);

int ans[MXX],a[MXX],b[MXX],n,blo[MXX],len,blocnt,qn,appeared[MXX],fstpos[MXX],lstpos[MXX],apn;

struct Query {
    int l,r,id;

    I bool operator < (const Query &co) const {
        Heriko (blo[l]==blo[co.l])?(r<co.r):(blo[l]<blo[co.l]);
    }
}

q[MXX];

int lst[MXX];

I int Clac_Faster_Than_SF1000(int l,int r) {
    int res(0);

    for(int i(l);i<=r;++i)
        lst[a[i]]=0;

    for(int i(l);i<=r;++i)
        if(!lst[a[i]])
            lst[a[i]]=i;
        else
            res=Hmax(res,i-lst[a[i]]);  

    Heriko res;
}

S main() {
    Files();

    fr(n),len=sqrt(n);

    for(int i(1);i<=n;++i)
        fr(a[i]),b[i]=a[i];

    sort(b+1,b+1+n);
    int nl(unique(b+1,b+1+n)-b-1);

    for(int i(1);i<=n;++i)
        a[i]=lower_bound(b+1,b+1+nl,a[i])-b;

    for(int i(1);i<=n;++i)
        blo[i]=(i-1)/len+1;

    blocnt=blo[n];

    fr(qn);

    for(int i(1);i<=qn;++i)
        fr(q[i].l),fr(q[i].r),q[i].id=i;

    sort(q+1,q+1+qn);
    int l(0),r(0),nw(1),tmpans(0);

    for(int i(1);i<=blocnt;++i) {
        int rx(Hmin(n,i*len));
        l=rx+1,r=rx,tmpans=0,apn=0;

        for(;blo[q[nw].l]==i;++nw) {
            if(blo[q[nw].r]==i)
                ans[q[nw].id]=Clac_Faster_Than_SF1000(q[nw].l,q[nw].r);
            else {
                while(r<q[nw].r) {
                    ++r;
                    lstpos[a[r]]=r;

                    if(!fstpos[a[r]])
                        fstpos[a[r]]=r,appeared[++apn]=a[r];

                    tmpans=Hmax(tmpans,r-fstpos[a[r]]);
                }

                int lsttmp(tmpans);

                while(l>q[nw].l) {
                    --l;

                    if(lstpos[a[l]])
                        tmpans=Hmax(tmpans,lstpos[a[l]]-l);
                    else
                        lstpos[a[l]]=l;
                }

                ans[q[nw].id]=tmpans;

                while(l<=rx) {
                    if(lstpos[a[l]]==l)
                        lstpos[a[l]]=0;

                    ++l;
                }

                tmpans=lsttmp;
            }
        }

        for(int i(1);i<=apn;++i)
            fstpos[appeared[i]]=lstpos[appeared[i]]=0;
    }

    for(int i(1);i<=qn;++i)
        fw(ans[i],1);

    Heriko Deltana;
}

「例题二」AT1219 歴史の研究

原题链接:AtCoder-JOI2014 歴史の研究

洛谷链接:AT1219 歴史の研究

「例题二」题目简述

给出长度为 \(N\) 的序列,\(Q\) 次询问,每次询问区间 \([L,R]\) 中最大的重要度。

重要度的定义为当前事件的权值 \(X_i\) 乘上事件在区间中出现次数 \(T_i.\)

「例题二」思路简述

和上个题一样,这个题添加操作也是很好实现的,维护一个桶即可,删除操作一样的不能实现,所以我们用同样的策略。

「例题二」Code

template<typename J>
I J Hmax(const J &x,const J &y) {
    Heriko x>y?x:y;
}

template<typename J>
I J Hmin(const J &x,const J &y) {
    Heriko x<y?x:y;
}

CI MXX(2e5+1);

int a[MXX],b[MXX],lx[MXX],rx[MXX],blo[MXX],n,qn,len,blocnt,cnt[MXX],co[MXX];

LL ans[MXX],tmpans;

struct Query {
    int l,r,id;

    I bool operator < (const Query &co) const {
        Heriko blo[l]==blo[co.l]?r<co.r:l<co.l;
    }
}

q[MXX];

I void Add(int x) {
    ++cnt[a[x]];
    tmpans=Hmax(tmpans,(LL)cnt[a[x]]*b[a[x]]);
}

S main() {
    Files();

    fr(n),fr(qn),len=sqrt(n),blocnt=n/len;

    for(int i(1);i<=n;++i)
        fr(a[i]),b[i]=a[i];

    for(int i(1);i<=qn;++i)
        fr(q[i].l),fr(q[i].r),q[i].id=i;

    sort(b+1,b+1+n);
    int nl(unique(b+1,b+1+n)-b-1);

    for(int i(1);i<=n;++i)
        a[i]=lower_bound(b+1,b+1+nl,a[i])-b;

    for(int i(1);i<=n;++i)
        blo[i]=(i-1)/len+1;

    for(int i(1);i<=blocnt;++i)
        lx[i]=rx[i-1]+1,rx[i]=lx[i]+len-1;

    if(rx[blocnt]<n)
        ++blocnt,lx[blocnt]=rx[blocnt-1]+1,rx[blocnt]=n;//这里用了一种和前面不同的处理每个块端点的方法,都不难写

    int l(0),r(0),nw(1);
    sort(q+1,q+1+qn);

    for(int i(1);i<=blocnt;++i) {
        mst(cnt,0);
        r=rx[i],tmpans=0;

        while(blo[q[nw].l]==i) {
            l=rx[i]+1;

            if(q[nw].r-q[nw].l<=len) {
                
                mst(co,0);
                LL anothertmpans(0);

                for(int i(q[nw].l);i<=q[nw].r;++i)
                    ++co[a[i]];

                for(int i(q[nw].l);i<=q[nw].r;++i)
                    anothertmpans=Hmax(anothertmpans,(LL)co[a[i]]*b[a[i]]);

                for(int i(q[nw].l);i<=q[nw].r;++i)
                    --co[a[i]];

                ans[q[nw].id]=anothertmpans;
            }
            else {
                while(q[nw].r>r)
                    Add(++r);

                LL lsttmp(tmpans);

                while(q[nw].l<l)
                    Add(--l);

                ans[q[nw].id]=tmpans;
                tmpans=lsttmp;

                while(l<=rx[i])
                    --cnt[a[l++]];
            }

            ++nw;
        }
    }

    for(int i(1);i<=qn;++i)
        fw(ans[i],1);

    Heriko Deltana;
}

终了

终了。

上一篇:python爬虫之requests模块


下一篇:Java类初始化