本文移植自个人的原博客（原文）

题目链接

Luogu 2042

题目描述

题解

对于删除操作和插入操作，应将删除区间左边一位的端点旋转到根，再将区间右边一位的端点旋转到根的右儿子（对于插入操作则为将插入位置前一位旋转到根，后一位旋转到其右儿子），需要注意的是，插入元素时应按顺序建立尽量平衡的结构，而不应直接插入（这样初始形态就会变成一条链），否则会导致时间复杂度过高，同时操作后也要注意更新信息。

对于修改操作和反转操作，可以借鉴线段树的懒人标记，在进行形如删除操作的旋转后，将操作区间打上标记，将深度最浅的节点进行操作，然后在待该子树变动时再下传标记。

对于求和操作，具体实现与线段树相同。

对于求最大子串和的操作，可以其具体实现与动规相同，只是在其他操作中实时更新，这样便可以做到$O(1)$查询。

（一开始写了个几近暴力的实现，后两个操作都是遍历一遍后才能得到答案。数据范围中虽然说明最多会插入$4e6$个元素，但同时也说明队列中最多只有$5e5$个元素，对此可以进行空间上的优化，将被删除元素的下标标记下来，添加时重新使用）

V1（暴力）

#include<iostream>
#include<cstdio>
const int N = 4e6+5;
const int inf = 0x7fffffff;
using namespace std;
int tot,root,rev[N],size[N],w[N],fa[N],son[N][2],id[N];
void update(int x)
{
    size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
void pushdown(int x)
{
    if(rev[x])
    {
        swap(son[x][0],son[x][1]);
        rev[son[x][0]]^=1;
        rev[son[x][1]]^=1;
        rev[x]=0;
    }
    return;
}
void zg(int x)
{
    pushdown(fa[x]),pushdown(x);
    int y=fa[x],z=fa[y],t=(son[y][0]==x);
    if(z) son[z][son[z][1]==y]=x;fa[x]=z;
    son[y][!t]=son[x][t];fa[son[y][!t]]=y;
    son[x][t]=y;fa[y]=x;
    update(y);update(x);
}
void splay(int x,int f)
{
    while(fa[x]!=f)
    {
        int y=fa[x],z=fa[y];
        if(z!=f)
        {
            if(son[z][0]==y^son[y][0]==x) zg(x);
            else zg(y);
        } 
        zg(x);    
    }
    if(!f) root=x;
}
void insert(int &x,int v,int f)
{
    if(!x)
    {
        x=++tot;
        son[x][0]=son[x][1]=0;
        size[x]=1;
        w[x]=v;fa[x]=f;
        splay(x,0);
        return;
    }
    insert(son[x][v>w[x]],v,x);
    update(x);
}
int get(int v)
{
    int x=root;
    while(x&&v!=w[x]) x=son[x][v>w[x]];
    return x;
}
int find(int k,int rank)
{
    pushdown(k);
    int l=son[k][0],r=son[k][1];
    if(size[l]+1==rank)return k;
    else if(size[l]>=rank)return find(l,rank);
    else return find(r,rank-size[l]-1);
}
int a[N];
char op[19];
int sum1,ans1,max1;
int inorder(int x)
{
    pushdown(x);
    if(son[x][0])inorder(son[x][0]);
    if(w[x]!=inf&&w[x]!=-inf)printf("%d ",a[w[x]]);
    if(son[x][1])inorder(son[x][1]);
}
int inordermax(int x)
{
    pushdown(x);
    if(son[x][0])inordermax(son[x][0]);
    if(w[x]!=inf&&w[x]!=-inf)
    {
        max1=max(max1,a[w[x]]);
        sum1+=a[w[x]]*num[x];
        if(sum1>0)ans1=max(ans1,sum1);
        else    sum1=0;
    }
    if(son[x][1])inordermax(son[x][1]);
}

int main()
{
//    freopen("seq2005.in","r",stdin);
//    freopen("seq2005.out","w",stdout);
    int n,m,tmp;
    scanf("%d%d",&n,&m);
    insert(root,-inf,0);insert(root,inf,0);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1;i<=n;++i)insert(root,i,0);
    tmp=n;
    for(int i=1,pos,tt,x;i<=m;++i)
    {
        scanf("%s",op);
        if(op[0]=='I')
        {
            scanf("%d%d",&pos,&tt);
            int now=find(root,pos+1),ne=find(root,pos+2);
            update(now),update(ne);
            splay(now,0);splay(ne,root);
            for(int i=1;i<=tt;++i)scanf("%d",&a[++tmp]),insert(son[ne][0],tmp,ne);
            update(root),update(son[root][1]);
        }
        if(op[0]=='D')
        {
            scanf("%d%d",&pos,&tt);
            int now=find(root,pos),ne=find(root,pos+tt+1);
            splay(now,0);splay(ne,root);
            fa[son[ne][0]]=0;
            son[ne][0]=0;
            update(ne);update(now);
        }
        if(op[0]=='M'&&op[2]=='K')
        {
            scanf("%d%d%d",&pos,&tt,&x);
            for(int t=pos+1;t<=pos+tt;++t)
            a[w[find(root,t)]]=x;
        }
        if(op[0]=='R')
        {
            scanf("%d%d",&pos,&tt);
            int now=find(root,pos),ne=find(root,pos+tt+1);
            update(now),update(ne);
            splay(now,0);splay(ne,root);
            int s=son[ne][0];
            rev[s]^=1;
        }
        if(op[0]=='G')
        {
            scanf("%d%d",&pos,&tt);
            int sum=0;
            for(int t=1;t<=tt;++t)
            sum+=a[find(root,pos+t)-2];
            printf("%d\n",sum);
        }
        if(op[0]=='M'&&op[2]=='X')
        {
            sum1=ans1=0;max1=-0x7fffffff;
            inordermax(root);
            printf("%d\n",ans1==0?max1:ans1);
        }
    }
    //    inorder(root);
}

V2（正解）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf = 1e9;
const int N = 1e6+1;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,root,cnt;
int sum[N],size[N],v[N],mx[N],lx[N],rx[N],a[N],id[N],fa[N],son[N][2];;
bool tag[N],rev[N];
queue<int>q;
void pushdown(int x)
{
    int sonl=son[x][0],sonr=son[x][1];
    if(tag[x])
    {

        if(sonl)tag[sonl]=true,v[sonl]=v[x],sum[sonl]=v[x]*size[sonl];
        if(sonr)tag[sonr]=true,v[sonr]=v[x],sum[sonr]=v[x]*size[sonr];
        if(v[x]>=0)
        {
            if(sonl)lx[sonl]=rx[sonl]=mx[sonl]=sum[sonl];
            if(sonr)lx[sonr]=rx[sonr]=mx[sonr]=sum[sonr];
        }
        else 
        {
            if(sonl)lx[sonl]=rx[sonl]=0,mx[sonl]=v[x];
            if(sonr)lx[sonr]=rx[sonr]=0,mx[sonr]=v[x];
        }
        rev[x]=tag[x]=0;
    }
    if(rev[x])
    {
        rev[x]^=1;rev[sonl]^=1;rev[sonr]^=1;
        swap(lx[sonl],rx[sonl]);swap(lx[sonr],rx[sonr]);
        swap(son[sonl][0],son[sonl][1]);swap(son[sonr][0],son[sonr][1]);
    }
}
int inorder(int x)
{
    pushdown(x);
    if(son[x][0])inorder(son[x][0]);
    if(v[x]!=inf&&v[x]!=-inf)printf("%d ",v[x]);
    if(son[x][1])inorder(son[x][1]);
}
void update(int x)
{
    int sonl=son[x][0],sonr=son[x][1];
    sum[x]=sum[sonl]+sum[sonr]+v[x];
    size[x]=size[sonl]+size[sonr]+1;
    mx[x]=max(mx[sonl],mx[sonr]);
    mx[x]=max(mx[x],rx[sonl]+v[x]+lx[sonr]);
    lx[x]=max(lx[sonl],sum[sonl]+v[x]+lx[sonr]);
    rx[x]=max(rx[sonr],sum[sonr]+v[x]+rx[sonl]);
}

void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l,r;
    l=(son[y][1]==x);r=l^1;
    if(y==k)k=x;
    else son[z][son[z][1]==y]=x;
    fa[son[x][r]]=y;fa[y]=x;fa[x]=z;
    son[y][l]=son[x][r];son[x][r]=y;
    update(y);update(x);
}
void splay(int x,int &k)
{
    while(x!=k)
    {
        int y=fa[x],z=fa[y];
        if(y!=k)
        {
            if(son[y][0]==x^son[z][0]==y)rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}
int find(int x,int rk)
{
    pushdown(x);
    int l=son[x][0],r=son[x][1];
    if(size[l]+1==rk)return x;
    if(size[l]>=rk)return find(l,rk);
    return find(r,rk-size[l]-1);
}
void rec(int x)
{
    if(!x)return;
    int l=son[x][0],r=son[x][1];
    rec(l);rec(r);q.push(x);
    fa[x]=son[x][0]=son[x][1]=0;
    tag[x]=rev[x]=0;
}
int split(int k,int tt)
{
    int x=find(root,k),y=find(root,k+tt+1);
    splay(x,root);splay(y,son[x][1]);
    return son[y][0];
}
void modify(int k,int tt,int val)
{
    int x=split(k,tt),y=fa[x];
    v[x]=val;tag[x]=1;sum[x]=size[x]*val;
    if(val>=0)lx[x]=rx[x]=mx[x]=sum[x];
    else lx[x]=rx[x]=0,mx[x]=val;
    update(y);update(fa[y]);
}
void rever(int k,int tt)
{
    int x=split(k,tt),y=fa[x];
    if(!tag[x])
    {
        rev[x]^=1;
        swap(son[x][0],son[x][1]);
        swap(lx[x],rx[x]);
        update(y);update(fa[y]);
    }
}
void delet(int k,int tt)
{
    int x=split(k,tt),y=fa[x];
    rec(x);son[y][0]=0;
    update(y);update(fa[y]);
}
void build(int l,int r,int s)
{
    if(l>r)return;
    int mid=(l+r)>>1,now=id[mid],last=id[s];
    if(l==r)
    {
        sum[now]=a[l];size[now]=1;
        tag[now]=rev[now]=0;
        if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l];
        else lx[now]=rx[now]=0,mx[now]=a[l];
    }
    else build(l,mid-1,mid),build(mid+1,r,mid);
    v[now]=a[mid];fa[now]=last;update(now);
    son[last][mid>=s]=now;
   }
void insert(int k,int tt)
{
    for(int i=1;i<=tt;i++)a[i]=read();
    for(int i=1;i<=tt;i++)
    if(!q.empty())id[i]=q.front(),q.pop();
    else id[i]=++cnt;
    build(1,tt,0);int z=id[(1+tt)>>1];
    int x=find(root,k+1),y=find(root,k+2);
    splay(x,root);splay(y,son[x][1]);
    fa[z]=y;son[y][0]=z;
    update(y);update(x);
}
int main()
{
//    freopen("seq2005.in","r",stdin);
//    freopen("seq2005.out","w",stdout);
    scanf("%d%d",&n,&m);
    mx[0]=a[1]=a[n+2]=-inf;
    for(int i=2;i<=n+1;i++)a[i]=read();
    for(int i=1;i<=n+2;i++)id[i]=i;
    build(1,n+2,0);
    root=(n+3)>>1;cnt=n+2;
    int k,tt,val;
    char op[19];
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        if(op[0]=='I')k=read(),tt=read(),insert(k,tt);
        if(op[0]=='D')k=read(),tt=read(),delet(k,tt);
        if(op[0]=='M'&&op[2]=='X')printf("%d\n",mx[root]);
        if(op[0]=='M'&&op[2]=='K')k=read(),tt=read(),val=read(),modify(k,tt,val);
        if(op[0]=='R')k=read(),tt=read(),rever(k,tt);
        if(op[0]=='G'){k=read(),tt=read();printf("%d\n",sum[split(k,tt)]);}
    }
//        inorder(root);
}

NOI2005 维修数列

题目链接

题目描述

题解

V1（暴力）

V2（正解）