p2042 维修数列（SPLAY）-白红宇

p2042 维修数列（SPLAY）

阅读量：6322 次

发布时间：2019-06-22

本文共 7516 字，大约阅读时间需要 25 分钟。

终于yy过去了

撒花

调了一天半，出了无数锅

以下是出锅列表

rotate的时候要判断父亲节点的父亲节点是否存在

rotate的时候记得修改节点的父亲信息

pushdown的时候注意特判有无左右子树

本题最大子段和要求至少要有一个数字

splay的每个节点中都存有一个点的权值，和线段树不同

lx和rx可以为0

初始化哨兵节点的时候，哨兵节点的权值为-INF,否则会影响到最大子段和的询问

splay操作时候特判父亲节点的父亲节点是否是goal节点和父亲节点是否是goal节点，每次rorate后维护父亲的值

区间整体偏移加一不要忘记

val>=1不要打成tag>=1

newNode的时候lx,rx赋值成max(0,val)

findkth的时候注意pushdown

erase，makesame和insert后注意pushup

makesame时不仅要修改对应标记，还要修改对应节点的数值

Reverse的时候翻转lx,rx,还要翻转两颗子树，tag用^的方式下传,因为翻转两次等于没有翻转

回收节点时,标记记得清空
我果然还是太弱了
放一下丑陋无比的代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;struct SPTNode{    int son[2],val,sz,fa,Lmax,Rmax,partMax,Sum,SwapTag,SameTag;}SPT[550100];queue
        
          frees;int root,NumToIns[550100],n,m,a[550100];bool isrl(int o){//false is left : true is right    return SPT[SPT[o].fa].son[1]==o;}void pushup(int o){    SPT[o].sz=SPT[SPT[o].son[0]].sz+SPT[SPT[o].son[1]].sz+1;    SPT[o].Sum=SPT[SPT[o].son[0]].Sum+SPT[SPT[o].son[1]].Sum+SPT[o].val;    SPT[o].partMax=max(SPT[SPT[o].son[0]].partMax,max(SPT[SPT[o].son[1]].partMax,SPT[SPT[o].son[0]].Rmax+SPT[SPT[o].son[1]].Lmax+SPT[o].val));    SPT[o].Lmax=max(SPT[SPT[o].son[0]].Lmax,SPT[SPT[o].son[1]].Lmax+SPT[SPT[o].son[0]].Sum+SPT[o].val);    SPT[o].Rmax=max(SPT[SPT[o].son[1]].Rmax,SPT[SPT[o].son[0]].Rmax+SPT[SPT[o].son[1]].Sum+SPT[o].val);}void pushdown(int o){    if(o&&SPT[o].SameTag){        if(SPT[o].son[0]){            SPT[SPT[o].son[0]].SameTag=1;            SPT[SPT[o].son[0]].val=SPT[o].val;            SPT[SPT[o].son[0]].Sum=SPT[SPT[o].son[0]].val*SPT[SPT[o].son[0]].sz;            if(SPT[o].val>=0)                SPT[SPT[o].son[0]].Lmax=SPT[SPT[o].son[0]].Rmax=SPT[SPT[o].son[0]].partMax=SPT[SPT[o].son[0]].Sum;            else{                SPT[SPT[o].son[0]].Lmax=SPT[SPT[o].son[0]].Rmax=0;                SPT[SPT[o].son[0]].partMax=SPT[SPT[o].son[0]].val;            }                }        if(SPT[o].son[1]){            SPT[SPT[o].son[1]].SameTag=1;            SPT[SPT[o].son[1]].val=SPT[o].val;            SPT[SPT[o].son[1]].Sum=SPT[SPT[o].son[1]].val*SPT[SPT[o].son[1]].sz;            if(SPT[o].val>=0)                SPT[SPT[o].son[1]].Lmax=SPT[SPT[o].son[1]].Rmax=SPT[SPT[o].son[1]].partMax=SPT[SPT[o].son[1]].Sum;            else{                SPT[SPT[o].son[1]].Lmax=SPT[SPT[o].son[1]].Rmax=0;                SPT[SPT[o].son[1]].partMax=SPT[SPT[o].son[1]].val;            }        }        SPT[o].SameTag=SPT[o].SwapTag=0;    }    else if(o&&SPT[o].SwapTag){        if(SPT[o].son[0]){            SPT[SPT[o].son[0]].SwapTag^=1;            swap(SPT[SPT[o].son[0]].Lmax,SPT[SPT[o].son[0]].Rmax);            swap(SPT[SPT[o].son[0]].son[0],SPT[SPT[o].son[0]].son[1]);        }        if(SPT[o].son[1]){            SPT[SPT[o].son[1]].SwapTag^=1;            swap(SPT[SPT[o].son[1]].Lmax,SPT[SPT[o].son[1]].Rmax);            swap(SPT[SPT[o].son[1]].son[0],SPT[SPT[o].son[1]].son[1]);        }        SPT[o].SwapTag=0;    }}void rorate(int o){    int f=SPT[o].fa;    int g=SPT[f].fa;    int which=isrl(o);    pushdown(f);    pushdown(o);    SPT[f].son[which]=SPT[o].son[which^1];    SPT[SPT[f].son[which]].fa=f;    SPT[o].son[which^1]=f;    SPT[f].fa=o;    SPT[o].fa=g;    if(g)        SPT[g].son[SPT[g].son[1]==f]=o;    pushup(f);    pushup(o);}void splay(int o,int goal){    for(int f;(f=SPT[o].fa)!=goal;rorate(o))        if(SPT[f].fa!=goal)            rorate(isrl(f)==isrl(o)?f:o);    if(goal==0)        root=o;}int finds(int o,int kth){    if(!o)        return 0;    pushdown(o);    if(kth==SPT[SPT[o].son[0]].sz+1)        return o;    if(kth<=SPT[SPT[o].son[0]].sz)        return finds(SPT[o].son[0],kth);    else        return finds(SPT[o].son[1],kth-SPT[SPT[o].son[0]].sz-1);}int newNode(int fax,int valx){    int num=frees.front();    frees.pop();    SPT[num].Lmax=SPT[num].Rmax=max(0,valx);    SPT[num].partMax=valx;    SPT[num].SameTag=SPT[num].SwapTag=0;    SPT[num].Sum=valx;    SPT[num].fa=fax;    SPT[num].son[0]=SPT[num].son[1]=0;    SPT[num].sz=1;    SPT[num].val=valx;    return num;}void init(void){    for(int i=1;i<=550000;i++)        frees.push(i);}int build(int l,int r,int a[],int fa){    if(r
         
          >1; int numx=newNode(fa,a[mid]); SPT[numx].son[0]=build(l,mid-1,a,numx); SPT[numx].son[1]=build(mid+1,r,a,numx); pushup(numx); return numx;}void insert(void){ int posi,tot; scanf("%d %d",&posi,&tot); for(int i=1;i<=tot;i++) scanf("%d",&NumToIns[i]); int mergeroot=build(1,tot,NumToIns,0); int L=posi,R=posi+1; int lxx=finds(root,L+1),rxx=finds(root,R+1); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); SPT[SPT[root].son[1]].son[0]=mergeroot; SPT[mergeroot].fa=SPT[root].son[1]; pushup(SPT[root].son[1]); pushup(root);}void dfsRec(int u){ if(!u) return; pushdown(u); frees.push(u); dfsRec(SPT[u].son[0]); dfsRec(SPT[u].son[1]);}void del(void){ int posi,tot; scanf("%d %d",&posi,&tot); int L=posi,R=posi+tot; int lxx=finds(root,L),rxx=finds(root,R+1); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); dfsRec(SPT[SPT[root].son[1]].son[0]); SPT[SPT[root].son[1]].son[0]=0; pushup(SPT[root].son[1]); pushup(root);}void swapArr(void){ int posi,tot; scanf("%d %d",&posi,&tot); int L=posi,R=posi+tot; int lxx=finds(root,L),rxx=finds(root,R+1); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); if(!SPT[SPT[SPT[root].son[1]].son[0]].SameTag){ SPT[SPT[SPT[root].son[1]].son[0]].SwapTag^=1; swap(SPT[SPT[SPT[root].son[1]].son[0]].son[0],SPT[SPT[SPT[root].son[1]].son[0]].son[1]); swap(SPT[SPT[SPT[root].son[1]].son[0]].Lmax,SPT[SPT[SPT[root].son[1]].son[0]].Rmax); pushup(SPT[root].son[1]); pushup(root); }}void QuerySum(void){ int posi,tot; scanf("%d %d",&posi,&tot); int L=posi,R=posi+tot; int lxx=finds(root,L),rxx=finds(root,R+1); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); printf("%d\n",SPT[SPT[SPT[root].son[1]].son[0]].Sum);}void QueryPartMax(void){ printf("%d\n",SPT[root].partMax);}void MakeTheSame(void){ int posi,tot,cx; scanf("%d %d %d",&posi,&tot,&cx); int L=posi,R=posi+tot; int lxx=finds(root,L),rxx=finds(root,R+1); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); SPT[SPT[SPT[root].son[1]].son[0]].SameTag=1; SPT[SPT[SPT[root].son[1]].son[0]].val=cx; SPT[SPT[SPT[root].son[1]].son[0]].Sum=cx*SPT[SPT[SPT[root].son[1]].son[0]].sz; if(cx>=0) SPT[SPT[SPT[root].son[1]].son[0]].Lmax=SPT[SPT[SPT[root].son[1]].son[0]].Rmax=SPT[SPT[SPT[root].son[1]].son[0]].partMax=SPT[SPT[SPT[root].son[1]].son[0]].Sum; else{ SPT[SPT[SPT[root].son[1]].son[0]].Lmax=SPT[SPT[SPT[root].son[1]].son[0]].Rmax=0; SPT[SPT[SPT[root].son[1]].son[0]].partMax=cx; } pushup(SPT[root].son[1]); pushup(root);}void debug(void){ int xxxx; printf("getL="); scanf("%d",&xxxx); for(int posi=1;posi<=xxxx;posi++){ int L=posi,R=posi+1; int lxx=finds(root,L),rxx=finds(root,R+1); splay(lxx,0); splay(rxx,lxx); pushdown(root); printf("%d ",SPT[SPT[SPT[root].son[1]].son[0]].Sum); } printf("\n");}int main(){ init(); scanf("%d %d",&n,&m); for(int i=2;i<=n+1;i++) scanf("%d",&a[i]); a[1]=-0x3f3f3f3f; a[n+2]=-0x3f3f3f3f; SPT[0].partMax=-0x3f3f3f3f; root=build(1,n+2,a,0); char opt[20]; for(int i=1;i<=m;i++){ // debug(); scanf("%s",opt); if(opt[0]=='I'){ insert(); } else if(opt[0]=='D'){ del(); } else if(opt[0]=='M'&&opt[2]=='K'){ MakeTheSame(); } else if(opt[0]=='R'){ swapArr(); } else if(opt[0]=='G'){ QuerySum(); } else if(opt[0]=='M'&&opt[2]=='X'){ QueryPartMax(); } } return 0;}