洛谷P2710 数列/洛谷P2042/NOI2005 维护数列

@Pelom  November 8, 2019

题意

维护一个数列,共$7$种操作

  • 区间插入
  • 区间删除
  • 区间翻转
  • 区间覆盖
  • 区间求和
  • 单点查询
  • 区间最大连续子序列和

数据范围:$1 \le n \le 200000,1 \le m \le 20000$

题解

使用$\text{fhq-Treap}$维护
为每一个节点记录区间和与前缀/后缀/整体最大连续字段和,更新时考虑左右是否相接
注意最大连续字段和至少选一个

inline void node::pushUp(){
    siz=l.siz+1+r.siz; //大小
    sum=l.sum+val+r.sum; //区间和
    s[0]=max(0,max(l.s[0],l.sum+val+r.s[0])); //前缀
    s[1]=max(0,max(r.s[1],r.sum+val+l.s[1])); //后缀
    s[2]=max(max(0,l.s[1])+val+max(0,r.s[0]),max(l.s[2],r.s[2])); //整体
}

下传标记;两个标记并无优先级之分

inline void node::pushDown(){
    if(rev){ //处理翻转
        l.reverse();
        r.reverse();
        rev=0;
    }
    if(cvr!=114514){ //处理覆盖
        l.cover(cvr);
        r.cover(cvr);
        cvr=114514;
    }
}

插入删除对空间消耗过大,因此建立回收站:删除时将节点标号放入回收站(注意清空原来的信息);插入时先从回收站中取节点,若回收站为空,才新建节点

inline int newNode(int k){ //新建节点
    int u;
    if(tp)
        u=tsh[tp--]; //从回收站中取
    else u=++sz; //否则新建
    T[u].ch[0]=T[u].ch[1]=0;
    T[u].val=T[u].sum=T[u].s[2]=k;
    T[u].s[0]=T[u].s[1]=max(0,k);
    T[u].rnd=rand();
    T[u].siz=1;
    T[u].cvr=114514;
    T[u].rev=0;
    return u; //返回节点标号
}
void recycle(int u){ //回收
    if(!u)
        return ;
    recycle(ls);
    tsh[++tp]=u; //加入回收站
    recycle(rs);
}
inline void erase(int p,int len){ //区间删除
    split(rt,p+len-1,x,y);
    split(x,p-1,x,u);
    recycle(u); //回收
    rt=merge(x,y);
}

由于普通的建树(即一个个插入)是$O(n \log n)$的,因此采用笛卡尔式建树,复杂度为$O(n)$

inline int build(int *a,int len){ //笛卡尔式建树
    int top=0;
    stk[++top]=newNode(a[1]);
    for(int i=2;i<=len;i++){
        int lst=0;
        int u=newNode(a[i]);
        for(;top && T[stk[top]].rnd>T[u].rnd;){
            T[stk[top]].pushUp();
            lst=stk[top];
            top--;
        }
        T[u].ch[0]=lst;
        if(top)
            T[stk[top]].ch[1]=u;
        stk[++top]=u;
    }
    for(;top;)
        T[stk[top--]].pushUp();
    return stk[1]; //返回新建树的树根
}

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ls T[u].ch[0]
#define rs T[u].ch[1]
const int N=200000+10;
const int INF=0x3f3f3f3f;
const int SUP=0xc0c0c0c0;
int n,m;
int a[N];
char op[10];
int sz,tp,rt,x,y,u;
int tsh[N],stk[N];
inline int read(){
    int res=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        if(c=='-')
            f=-1;
    for(;isdigit(c);c=getchar())
        res=res*10+c-'0';
    return f*res;
}
struct node{
    #define l T[ch[0]]
    #define r T[ch[1]]
    int ch[2];
    int val,rnd,siz,cvr,sum,s[3];
    bool rev;
    inline node(){
        ch[0]=ch[1]=val=siz=sum=rev=0;
        cvr=114514;
        s[2]=SUP;
    }
    inline void reverse();
    inline void cover(int);
    inline void pushUp();
    inline void pushDown();
} T[N];
inline void node::reverse(){
    if(this==T)
        return ;
    swap(ch[0],ch[1]);
    swap(s[0],s[1]);
    rev^=1;
}
inline void node::cover(int k){
    if(this==T)
        return ;
    val=k;
    sum=k*siz;
    s[2]=max(val,sum);
    s[0]=s[1]=max(0,sum);
    cvr=k;
}
inline void node::pushUp(){
    siz=l.siz+1+r.siz;
    sum=l.sum+val+r.sum;
    s[0]=max(0,max(l.s[0],l.sum+val+r.s[0]));
    s[1]=max(0,max(r.s[1],r.sum+val+l.s[1]));
    s[2]=max(max(0,l.s[1])+val+max(0,r.s[0]),max(l.s[2],r.s[2]));
}
inline void node::pushDown(){
    if(rev){
        l.reverse();
        r.reverse();
        rev=0;
    }
    if(cvr!=114514){
        l.cover(cvr);
        r.cover(cvr);
        cvr=114514;
    }
}
inline int rand(){
    static int seed=233;
    return seed=(int)seed*0x75d97LL%0x7fffffff;
}
inline int newNode(int k){
    int u;
    if(tp)
        u=tsh[tp--];
    else u=++sz;
    T[u].ch[0]=T[u].ch[1]=0;
    T[u].val=T[u].sum=T[u].s[2]=k;
    T[u].s[0]=T[u].s[1]=max(0,k);
    T[u].rnd=rand();
    T[u].siz=1;
    T[u].cvr=114514;
    T[u].rev=0;
    return u;
}
void split(int u,int k,int& x,int& y){
    if(!u){
        x=y=0;
        return ;
    }
    T[u].pushDown();
    if(k<=T[ls].siz){
        y=u;
        split(ls,k,x,ls);
    }
    else{
        x=u;
        split(rs,k-T[ls].siz-1,rs,y);
    }
    T[u].pushUp();
}
int merge(int x,int y){
    if(!x || !y)
        return x|y;
    if(T[x].rnd<T[y].rnd){
        T[x].pushDown();
        T[x].ch[1]=merge(T[x].ch[1],y);
        T[x].pushUp();
        return x;
    }
    else{
        T[y].pushDown();
        T[y].ch[0]=merge(x,T[y].ch[0]);
        T[y].pushUp();
        return y;
    }
}
inline int build(int *a,int len){
    int top=0;
    stk[++top]=newNode(a[1]);
    for(int i=2;i<=len;i++){
        int lst=0;
        int u=newNode(a[i]);
        for(;top && T[stk[top]].rnd>T[u].rnd;){
            T[stk[top]].pushUp();
            lst=stk[top];
            top--;
        }
        T[u].ch[0]=lst;
        if(top)
            T[stk[top]].ch[1]=u;
        stk[++top]=u;
    }
    for(;top;)
        T[stk[top--]].pushUp();
    return stk[1];
}
void recycle(int u){
    if(!u)
        return ;
    recycle(ls);
    tsh[++tp]=u;
    recycle(rs);
}
inline void insert(int p,int *a,int len){
    split(rt,p,x,y);
    rt=merge(x,merge(build(a,len),y));
}
inline void erase(int p,int len){
    split(rt,p+len-1,x,y);
    split(x,p-1,x,u);
    recycle(u);
    rt=merge(x,y);
}
inline void reverse(int p,int len){
    split(rt,p+len-1,x,y);
    split(x,p-1,x,u);
    T[u].reverse();
    rt=merge(x,merge(u,y));
}
inline void cover(int p,int len,int k){
    split(rt,p+len-1,x,y);
    split(x,p-1,x,u);
    T[u].cover(k);
    rt=merge(x,merge(u,y));
}
inline node query(int p,int len){
    split(rt,p+len-1,x,y);
    split(x,p-1,x,u);
    node res=T[u];
    rt=merge(x,merge(u,y));
    return res;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    rt=build(a,n);
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        switch(op[0]+op[3]){
            case 'I'+'E': //INSERT
                x=read(),n=read();
                for(int i=1;i<=n;i++)
                    a[i]=read();
                insert(x,a,n);
                break;
            case 'D'+'E': //DELETE
                x=read(),n=read();
                erase(x,n);
                break;
            case 'R'+'E': //REVERSE
                x=read(),n=read();
                reverse(x,n);
                break;
            case 'M'+'E': //MAKE-SAME
                x=read(),n=read(),y=read();
                cover(x,n,y);
                break;
            case 'G'+'-': //GET-SUM
                x=read(),n=read();
                printf("%d\n",query(x,n).sum);
                break;
            case 'G': //GET
                x=read();
                printf("%d\n",query(x,1).val);
                break;
            case 'M'+'-': //MAX-SUM
                x=read(),n=read();
                printf("%d\n",query(x,n).s[2]);
                break;
        }
    }
    return 0;
}

添加新评论