请写一个程序，要求维护一个数列，支持以下 6 种操作：

请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格

太神啦太神啦，我也不会做，我也是copycat的啊。

直接看上面这位神犇的题解吧。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=1e6+10;const int INF=1e9;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}char s[101];int fa[N],tr[N][2],key[N],size[N],mx[N];int root,sz,a[N],id[N],sum[N],lx[N],rx[N];bool rev[N],tag[N];queue
            
             q;inline void pushup(int x){ int l=tr[x][0],r=tr[x][1]; sum[x]=sum[l]+sum[r]+key[x]; size[x]=size[l]+size[r]+1; mx[x]=max(mx[l],max(mx[r],rx[l]+key[x]+lx[r])); lx[x]=max(lx[l],sum[l]+key[x]+lx[r]); rx[x]=max(rx[r],sum[r]+key[x]+rx[l]);}inline void pushdown(int x){ int l=tr[x][0],r=tr[x][1]; if(tag[x]){ rev[x]=tag[x]=0; if(l)tag[l]=1,key[l]=key[x],sum[l]=key[x]*size[l]; if(r)tag[r]=1,key[r]=key[x],sum[r]=key[x]*size[r]; if(key[x]>=0){ if(l)lx[l]=rx[l]=mx[l]=sum[l]; if(r)lx[r]=rx[r]=mx[r]=sum[r]; }else{ if(l)lx[l]=rx[l]=0,mx[l]=key[x]; if(r)lx[r]=rx[r]=0,mx[r]=key[x]; } } if(rev[x]){ rev[x]=0;rev[l]^=1;rev[r]^=1; swap(lx[l],rx[l]);swap(lx[r],rx[r]); swap(tr[l][0],tr[l][1]);swap(tr[r][0],tr[r][1]); }}inline bool get(int x){ return tr[fa[x]][1]==x;}inline void rotate(int x){ int y=fa[x],z=fa[y],which=get(x); tr[y][which]=tr[x][which^1];fa[tr[y][which]]=y; fa[y]=x;tr[x][which^1]=y;fa[x]=z; if(z)tr[z][tr[z][1]==y]=x; pushup(y);pushup(x); return;}inline void splay(int x,int y){ int f=fa[x]; while(f!=y){ if(fa[f]!=y)rotate(get(x)==get(f)?f:x); rotate(x);f=fa[x]; } if(!y)root=x; return;}inline int findx(int x){ //找到排名为x的点 int now=root; while(233){ pushdown(now); if(tr[now][0]&&x<=size[tr[now][0]])now=tr[now][0]; else{ int temp=(tr[now][0]?size[tr[now][0]]:0)+1; if(x==temp)return now; x-=temp;now=tr[now][1]; } }}inline int split(int k,int tot){ int x=findx(k),y=findx(k+tot+1); splay(x,0);splay(y,x); return tr[y][0];}inline void query(int k,int tot){ int x=split(k,tot); printf("%d\n",sum[x]);}inline void modify(int k,int tot,int v){ int x=split(k,tot),y=fa[x]; key[x]=v;tag[x]=1;sum[x]=size[x]*v; if(v>=0)lx[x]=rx[x]=mx[x]=sum[x]; else lx[x]=rx[x]=0,mx[x]=v; pushup(y);pushup(fa[y]);}inline void turn(int k,int tot){ int x=split(k,tot),y=fa[x]; if(!tag[x]){ rev[x]^=1; swap(tr[x][0],tr[x][1]); swap(lx[x],rx[x]); pushup(y);pushup(fa[y]); } return;}inline void recycle(int x){ int &l=tr[x][0],&r=tr[x][1]; if(l)recycle(l); if(r)recycle(r); q.push(x); fa[x]=l=r=tag[x]=rev[x]=0;}inline void build(int l,int r,int f){ int mid=(l+r)>>1,now=id[mid],pre=id[f]; if(l==r){ mx[now]=sum[now]=a[l]; tag[now]=rev[now]=0; lx[now]=rx[now]=max(a[l],0); size[now]=1; } if(l
             
              =f]=now;}inline void insert(int k,int tot){ for(int i=1;i<=tot;i++)a[i]=read(); for(int i=1;i<=tot;i++){ if(!q.empty())id[i]=q.front(),q.pop(); else id[i]=++sz; } build(1,tot,0); int z=id[(1+tot)>>1]; int x=findx(k+1),y=findx(k+2); splay(x,0);splay(y,x); fa[z]=y;tr[y][0]=z; pushup(y);pushup(x); return;}inline void del(int k,int tot){ int x=split(k,tot),y=fa[x]; recycle(x);tr[y][0]=0; pushup(y);pushup(fa[y]); return;}int main(){ int n=read(),m=read(); 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;sz=n+2; for(int i=1;i<=m;i++){ scanf("%s",s); if(s[0]=='I'){ int k=read(),tot=read(); insert(k,tot); } if(s[0]=='D'){ int k=read(),tot=read(); del(k,tot); } if(s[0]=='M'){ if(s[2]=='X')printf("%d\n",mx[root]); else{ int k=read(),tot=read(),c=read(); modify(k,tot,c); } } if(s[0]=='R'){ int k=read(),tot=read(); turn(k,tot); } if(s[0]=='G'){ int k=read(),tot=read(); query(k,tot); } } return 0;}
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：

+++++++++++++++++++++++++++++++++++++++++++