题解 P2710 【数列】

破忆 · 2020-10-26 13:26:38 · 题解

【题意】

维护一个序列

支持插入、删除、翻转、覆盖、求和、求最大子段和操作

【分析】

经典数据结构题

没什么思维难度，直接上fhq-treap吧

明确需要维护的信息

翻转和覆盖，需要打两个懒标记

求和需要区间和

求最大子段和需要区间最大前缀、最大后缀与最大子段和

还有随机键值、区间大小、左右子树

struct fhq_treap{
    int rand,siz,rev,cov,son[2],val;
    LL max,s,l,r;
}t[maxt];

上传信息、下发标记

线段树和平衡树的基本操作，比较套路

IN void pushup(RE int k){
    t[k].siz=t[ls].siz+t[rs].siz+1;
    t[k].s=t[ls].s+t[rs].s+t[k].val;
    t[k].l=max(t[ls].l,max(0ll,t[ls].s+t[k].val+t[rs].l));
    t[k].r=max(t[rs].r,max(0ll,t[rs].s+t[k].val+t[ls].r));
    t[k].max=max((LL)t[k].val,t[ls].r+t[k].val+t[rs].l);
    if(ls) t[k].max=max(t[k].max,t[ls].max);
    if(rs) t[k].max=max(t[k].max,t[rs].max);
}

IN void pushdown(RE int k){
    if(t[k].cov!=INF){
        LL c=t[k].cov;
        if(ls) cov(ls,c);
        if(rs) cov(rs,c);
        t[k].cov=INF;
    }
    if(t[k].rev){
        if(ls) rev(ls);
        if(rs) rev(rs);
        t[k].rev=0;
    }
}

fhq-treap合并、分裂板子

int merge(RE int x,RE int y){
    if(!x||!y) return x+y;
    if(t[x].rand<t[y].rand){
        pushdown(x);
        t[x].son[1]=merge(t[x].son[1],y);
        pushup(x);
        return x;
    }
    else{
        pushdown(y);
        t[y].son[0]=merge(x,t[y].son[0]);
        pushup(y);
        return y;
    }
}

void splits(RE int now,RE int k,RE int &x,RE int &y){
    if(!now){
        x=y=0;
        return;
    }
    pushdown(now);
    if(k<=t[t[now].son[0]].siz){
        y=now;
        splits(t[y].son[0],k,x,t[y].son[0]);
        pushup(y);
    }
    else{
        x=now;
        splits(t[x].son[1],k-t[t[x].son[0]].siz-1,t[x].son[1],y);
        pushup(x);
    }
    pushup(now);
}

插入与删除

插入仿照线段树建树方式，而不是逐个插入，可以更平衡

删点时把没用的点存入栈，以便下次使用

IN int build(RE int k){
    RE int now=top?stk[top--]:++cnt;
    t[now].rand=rand();
    t[now].cov=INF;
    t[now].rev=0;
    t[now].son[0]=t[now].son[1]=0;
    t[now].max=t[now].s=t[now].val=k;
    t[now].l=t[now].r=max(k,0);
    t[now].siz=1;
    return now;
}
int build(RE int l,RE int r){
    if(l==r) return build(read());
    int x=build(l,mid),y=build(mid+1,r);
    return merge(x,y);
}

void del(RE int k){
    if(ls) del(ls);
    if(rs) del(rs);
    stk[++top]=k;
}
IN void del(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    del(y);
    rt=merge(x,z);
}

覆盖与翻转

分离出待操作区间，然后打上标记，顺便更新信息

IN void cov(RE int k,RE int c){
    t[k].cov=t[k].val=c;
    t[k].s=(LL)t[k].siz*c;
    t[k].l=t[k].r=max(0ll,t[k].s);
    t[k].max=max((LL)c,t[k].s);
}

IN void cover(RE int l,RE int r,RE int c){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    cov(y,c);
    rt=merge(merge(x,y),z);
}

IN void rev(RE int k){
    if(!k) return;
    swap(t[k].l,t[k].r);
    swap(t[k].son[0],t[k].son[1]);
    t[k].rev^=1;
}
IN void reverse(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    rev(y);
    rt=merge(merge(x,y),z);
}

询问

分离出区间输出即可

IN LL query(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    RE LL ret=t[y].s;
    rt=merge(merge(x,y),z);
    return ret;
}

IN LL maxs(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    LL ret=t[y].max;
    rt=merge(merge(x,y),z);
    return ret;
}

算法

fhq-treap

提醒

细节多，代码长

以下几个地方值得注意

翻转时要交换最大前缀和最大后缀

下传标记时，先覆盖再翻转

建树时，先提取出子树再合并，不能写成这样，否则会有意想不到的错误

merge(build(l,mid),build(mid+1,r))

若没有覆盖标记时，懒标记应该设置成一个不可能出现的值，设成-1,0之类的就完了

记得开longlong

代码

#include<bits/stdc++.h>
#define LL long long
#define ls t[k].son[0]
#define rs t[k].son[1]
#define mid (l+r>>1)
#define IN inline
#define RE register
using namespace std;
const int maxt=5e5+5,INF=1<<30;
int n,m;
int top,stk[maxt];
int cnt,rt;
char z[15];
struct fhq_treap{
    int rand,siz,rev,cov,son[2],val;
    LL max,s,l,r;
}t[maxt];
IN int read(){
    RE int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
IN void rev(RE int k){
    if(!k) return;
    swap(t[k].l,t[k].r);
    swap(t[k].son[0],t[k].son[1]);
    t[k].rev^=1;
}
IN void cov(RE int k,RE int c){
    t[k].cov=t[k].val=c;
    t[k].s=(LL)t[k].siz*c;
    t[k].l=t[k].r=max(0ll,t[k].s);
    t[k].max=max((LL)c,t[k].s);
}
IN void pushup(RE int k){
    t[k].siz=t[ls].siz+t[rs].siz+1;
    t[k].s=t[ls].s+t[rs].s+t[k].val;
    t[k].l=max(t[ls].l,max(0ll,t[ls].s+t[k].val+t[rs].l));
    t[k].r=max(t[rs].r,max(0ll,t[rs].s+t[k].val+t[ls].r));
    t[k].max=max((LL)t[k].val,t[ls].r+t[k].val+t[rs].l);
    if(ls) t[k].max=max(t[k].max,t[ls].max);
    if(rs) t[k].max=max(t[k].max,t[rs].max);
}
IN void pushdown(RE int k){
    if(t[k].cov!=INF){
        LL c=t[k].cov;
        if(ls) cov(ls,c);
        if(rs) cov(rs,c);
        t[k].cov=INF;
    }
    if(t[k].rev){
        if(ls) rev(ls);
        if(rs) rev(rs);
        t[k].rev=0;
    }
}
void splits(RE int now,RE int k,RE int &x,RE int &y){
    if(!now){
        x=y=0;
        return;
    }
    pushdown(now);
    if(k<=t[t[now].son[0]].siz){
        y=now;
        splits(t[y].son[0],k,x,t[y].son[0]);
        pushup(y);
    }
    else{
        x=now;
        splits(t[x].son[1],k-t[t[x].son[0]].siz-1,t[x].son[1],y);
        pushup(x);
    }
    pushup(now);
}
int merge(RE int x,RE int y){
    if(!x||!y) return x+y;
    if(t[x].rand<t[y].rand){
        pushdown(x);
        t[x].son[1]=merge(t[x].son[1],y);
        pushup(x);
        return x;
    }
    else{
        pushdown(y);
        t[y].son[0]=merge(x,t[y].son[0]);
        pushup(y);
        return y;
    }
}
IN int build(RE int k){
    RE int now=top?stk[top--]:++cnt;
    t[now].rand=rand();
    t[now].cov=INF;
    t[now].rev=0;
    t[now].son[0]=t[now].son[1]=0;
    t[now].max=t[now].s=t[now].val=k;
    t[now].l=t[now].r=max(k,0);
    t[now].siz=1;
    return now;
}
void del(RE int k){
    if(ls) del(ls);
    if(rs) del(rs);
    stk[++top]=k;
}
int build(RE int l,RE int r){
    if(l==r) return build(read());
    int x=build(l,mid),y=build(mid+1,r);
    return merge(x,y);
}
IN void del(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    del(y);
    rt=merge(x,z);
}
IN void cover(RE int l,RE int r,RE int c){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    cov(y,c);
    rt=merge(merge(x,y),z);
}
IN void reverse(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    rev(y);
    rt=merge(merge(x,y),z);
}
IN LL query(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    RE LL ret=t[y].s;
    rt=merge(merge(x,y),z);
    return ret;
}
IN LL maxs(RE int l,RE int r){
    RE int x,y,z;
    splits(rt,r,x,z);
    splits(x,l-1,x,y);
    LL ret=t[y].max;
    rt=merge(merge(x,y),z);
    return ret;
}
int main(){
    freopen("P2710.in","r",stdin);
    freopen("P2710.out","w",stdout);
    n=read(),m=read();
    rt=build(1,n);
    for(RE int i=1;i<=m;i++){
        scanf("%s",z);
        if(z[0]=='I'){
            RE int pos=read(),tot=read();
            RE int x,y;
            splits(rt,pos,x,y);
            rt=merge(merge(x,build(pos,pos+tot-1)),y);
        }else
        if(z[0]=='D'){
            RE int pos=read(),tot=read();
            del(pos,pos+tot-1);
        }else
        if(z[0]=='R'){
            RE int pos=read(),tot=read();
            reverse(pos,pos+tot-1);
        }else
        if(z[2]=='K'){
            RE int pos=read(),tot=read(),c=read();
            cover(pos,pos+tot-1,c);
        }else
        if(z[1]=='A'){
            RE int pos=read(),tot=read();
            printf("%lld\n",maxs(pos,pos+tot-1));
        }else
        if(strlen(z)>4){
            RE int pos=read(),tot=read();
            printf("%lld\n",query(pos,pos+tot-1));
        }
        else{
            RE int pos=read();
            printf("%lld\n",query(pos,pos));
        }
    }
    return 0;
}

最后

保持一个平和的心态