splay入门题。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;#define LL long long#define FILE "dealing"#define mid ((l+r)>>1)#define pii pair
               
                #define up(i,j,n) for(int i=(j);i<=(n);i++)LL read(){ LL x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f*x;}const int maxn=605000,inf=1000000000;int n,m;int a[maxn];int fa[maxn],c[maxn][2],sum[maxn],lm[maxn],rm[maxn],Max[maxn],rev[maxn],f[maxn],q[maxn],siz[maxn],val[maxn],h[maxn],root,head=1,tail=0;void updata(int x){//updata sum siz maxse if(!x)return; siz[x]=siz[c[x][0]]+siz[c[x][1]]+1; h[x]=max(h[c[x][0]],h[c[x][1]]);h[x]=max(h[x],val[x]); sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x]; lm[x]=max(lm[c[x][0]],sum[c[x][0]]+val[x]+lm[c[x][1]]); rm[x]=max(rm[c[x][1]],sum[c[x][1]]+val[x]+rm[c[x][0]]); Max[x]=max(Max[c[x][0]],Max[c[x][1]]); Max[x]=max(Max[x],rm[c[x][0]]+val[x]+lm[c[x][1]]);}inline void add(int x){q[++tail]=x;if(tail==600000)tail=0;}inline int pop(){if(head==600001)head=1;return q[head++];}void change(int x,int c){ if(!x)return; val[x]=f[x]=h[x]=c; Max[x]=lm[x]=rm[x]=max(0,siz[x]*c); sum[x]=siz[x]*c;}void revv(int x){ if(!x)return;rev[x]^=1;swap(lm[x],rm[x]);swap(c[x][0],c[x][1]);}void pushdown(int x){ if(!x)return; if(rev[x])rev[x]=0,revv(c[x][0]),revv(c[x][1]); if(f[x]!=inf)change(c[x][0],f[x]),change(c[x][1],f[x]),f[x]=inf;}void rotate(int x){ if(!x)return; int y=fa[x],z=fa[y],d=c[y][1]==x; fa[y]=x,fa[x]=z;if(c[x][d^1])fa[c[x][d^1]]=y; c[y][d]=c[x][d^1];c[x][d^1]=y; if(z)c[z][c[z][1]==y]=x; updata(y),updata(x);}int p[maxn],top=0;void splay(int x,int S){ if(!x)return; for(int i=x;i;i=fa[i])p[++top]=i; while(top)pushdown(p[top--]); while(fa[x]!=S){ int y=fa[x],z=fa[y]; if(z!=S){ if((c[y][1]==x)^(c[z][1]==y))rotate(x); else rotate(y); } rotate(x); } if(!S)root=x;}int find(int k){//返回大于k个数的splay节点 int x=root; pushdown(x); while(siz[c[x][0]]!=k){ pushdown(x); if(siz[c[x][0]]>k)x=c[x][0]; else k=k-1-siz[c[x][0]],x=c[x][1]; } splay(x,0); return x;}int t[4000000];void build(int& x,int Fa,int l,int r){ if(l>r)return void(x=0); if(!x)x=pop(); lm[x]=rm[x]=Max[x]=max(0,h[x]=sum[x]=val[x]=t[mid]); fa[x]=Fa;siz[x]=1;f[x]=inf; if(l==r)return; build(c[x][0],x,l,mid-1); build(c[x][1],x,mid+1,r); updata(x);}void insert(int pos,int cnt){ int x=find(pos),y=find(pos+1); splay(x,0);splay(y,root); build(c[y][0],y,1,cnt); updata(y),updata(x);}void Det(int x){ if(!x)return; Det(c[x][0]);Det(c[x][1]); fa[x]=c[x][0]=c[x][1]=sum[x]=lm[x]=rm[x]=Max[x]=rev[x]=siz[x]=val[x]=0; f[x]=inf;h[x]=-inf; add(x);}void delet(int pos,int cnt){ int x=find(pos-1),y=find(pos+cnt); splay(x,0);splay(y,root); Det(c[y][0]);c[y][0]=0; updata(y),updata(x);}void Change(int pos,int cnt,int w){ int x=find(pos-1),y=find(pos+cnt); splay(x,0);splay(y,root); change(c[y][0],w); updata(y),updata(x);}void reverse(int pos,int cnt){ int x=find(pos-1),y=find(pos+cnt); splay(x,0);splay(y,root); revv(c[y][0]);updata(y),updata(x);}void getsum(int pos,int cnt){ int x=find(pos-1),y=find(pos+cnt); splay(x,0);splay(y,root); printf("%d\n",sum[c[y][0]]); updata(y),updata(x);}void maxseg(){ int x=find(0),y=find(siz[root]-1); splay(x,0);splay(y,root); printf("%d\n",(!Max[c[y][0]])?h[c[y][0]]:Max[c[y][0]]);}int main(){ //freopen("dealing.in","r",stdin); //freopen("dealing.out","w",stdout); n=read(),m=read(); memset(val,-10,sizeof(val));f[0]=inf; up(i,1,600000)add(i); t[1]=-inf,t[2]=inf; build(root,0,1,2);h[0]=-inf; up(i,1,n)t[i]=a[i]=read(); insert(0,n); char s[10];int pos,cnt,w; up(i,1,m){ scanf("%s",s); if(s[0]=='I'){ pos=read(),cnt=read(); up(j,1,cnt)t[j]=read(); if(!cnt)continue; insert(pos,cnt); } if(s[0]=='D'){ pos=read(),cnt=read(); if(!cnt)continue; delet(pos,cnt); } if(s[2]=='K'){ pos=read(),cnt=read(),w=read(); if(!cnt)continue; Change(pos,cnt,w); } if(s[0]=='R'){ pos=read(),cnt=read(); if(!cnt)continue; reverse(pos,cnt); } if(s[0]=='G'){ pos=read(),cnt=read(); if(!cnt){printf("0\n");continue;} getsum(pos,cnt); } if(s[2]=='X')maxseg(); } return 0;}