本文主要是介绍Splay 模板【NOI2005】 bzoj1500 维修数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
老师说写博客有助于学习和理解代码，所以从今天起，做一个写博客的人，面朝代码，春暖花开。
Splay是一种可以对一个数列进行区间修改，区间反转，查询最值，查询总和等操作的数据结构（我觉得Splay的结构类似于treap，功能类似于线段树），而且能够快速实现区间的分裂与合并。
Splay与Treap的最大区别是旋转方式，Treap将树按照堆得形式维护，只需要单旋。而Splay需要双旋，来保证时间复杂度为均摊O（log n）。
Spaly最主要的操作是伸展操作，即将某一个节点旋转到根节点处，主要依靠双旋来完成。
用Splay进行区间的分裂与合并可以通过伸展操作来构造。
————————————————Splay————————————————
NOI2005维修数列是一道Splay裸题，题目要求就是写一个程序要求维护一个数列，支持插入、删除、翻转、修改、查询区间和，查询最大子段这些操作。
插入和删除操作只需要把原序列分裂，插入或删除一段，再合并起来就可以。
翻转和修改只需要把需要操作的区间分离出来，打标记再合并。
查询区间和和最大字段，可以像线段树一样在每个Splay节点处维护区间最大和，左侧最大和，右侧最大和，区间总和。
最后把要查询的区间分裂出来查询就可以了。
注意事项：
1、如果合并函数返回一个指针的话，传参就不要打引用；
2、如果区间内全是负数，应该找最大的负数输出，所以maintain的时候要注意；
3、要时刻想着是否应该判断空节点（如果建立虚节点不必考虑此问题），因为分裂出来的区间或者将要用来合成的区间很有可能是NULL，防止RE；
4、使用指针和引用的时候要小心，尤其是当真正修改原指针的时候。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#define N 510002
#define INF 2147483647
#define Max(x,y) (x>y?x:y)
using namespace std;
int n,m,pos,tot,key;
int a[N];
char s[20];
struct splay
{splay *ch[2],*fa;int sz,val,ls,rs,ms,sum;int flip,lz;splay(int x)//构造函数{ch[0]=ch[1]=fa=NULL;sz=1;val=sum=ls=rs=ms=x;flip=0;lz=INF;}int cmp(int k){int z=1;if(ch[0]) z+=ch[0]->sz;if(k<z) return 0;if(k>z) return 1;return -1;}void push_down()//下传标记{if(flip==1){flip=0;swap(ch[0],ch[1]);swap(ls,rs);if(ch[0]) ch[0]->flip^=1;if(ch[1]) ch[1]->flip^=1;}if(lz!=INF){val=lz;sum=lz*sz;ls=rs=ms=lz>0?lz*sz:lz;if(ch[0]) ch[0]->lz=lz;if(ch[1]) ch[1]->lz=lz;lz=INF;}}void maintain()//维护节点信息{push_down();sz=1;sum=ms=ls=rs=val;if(ch[0]) {ch[0]->push_down();sz+=ch[0]->sz;sum+=ch[0]->sum;}if(ch[1]) {ch[1]->push_down();sz+=ch[1]->sz;sum+=ch[1]->sum;}if(!ch[0] && !ch[1]) return;else if(!ch[0] && ch[1]){ms=Max(Max(ms,val+ch[1]->ls),ch[1]->ms);ls=Max(ls,val+ch[1]->ls);rs=Max(ch[1]->rs,ch[1]->sum+val);}else if(ch[0] && !ch[1]){ms=Max(Max(ms,val+ch[0]->rs),ch[0]->ms);ls=Max(ch[0]->ls,ch[0]->sum+val);rs=Max(rs,ch[0]->rs+val);}else{ms=Max(Max(ms+Max(ch[0]->rs,0)+Max(ch[1]->ls,0),ch[0]->ms),ch[1]->ms);ls=Max(ch[0]->ls,ch[0]->sum+val+Max(ch[1]->ls,0));rs=Max(ch[1]->rs,ch[1]->sum+val+Max(ch[0]->rs,0));}}friend void turn(splay *&c,int d)//旋转{splay *y=c->ch[d^1];c->ch[d^1]=y->ch[d];if(y->ch[d]) y->ch[d]->fa=c;y->ch[d]=c; y->fa=c->fa;c->fa=y; c->maintain();c=y; c->maintain();}friend void splaying(splay *&c,int k)//伸展操作{c->push_down();int d=c->cmp(k);if(d==1) k-=c->sz-c->ch[1]->sz;if(d!=-1){splay *y=c->ch[d];y->push_down();int d2=y->cmp(k);if(d2==1) k-=y->sz-y->ch[1]->sz;if(d2!=-1){splaying(y->ch[d2],k);if(d==d2) turn(c,d^1);else turn(c->ch[d],d);}turn(c,d^1);}}friend void build_it(splay *&c,int l,int r)//将数组转成splay{if(l>r) return;int mid=(l+r)/2;c=new splay(a[mid]);build_it(c->ch[0],l,mid-1);build_it(c->ch[1],mid+1,r);if(c->ch[0]) c->ch[0]->fa=c;if(c->ch[1]) c->ch[1]->fa=c;c->maintain();}friend void dele(splay *&c)//删除操作{if(c->ch[0]) dele(c->ch[0]);if(c->ch[1]) dele(c->ch[1]);delete c;}friend splay* Merge(splay *x,splay *y)//合并{if(!x) return y;if(!y) return x;splaying(x,x->sz);x->ch[1]=y;if(y) y->fa=x;x->maintain();return x;}friend void Split(splay *V,int k,splay *&x,splay *&y)//分裂{if(k<=0) {x=NULL;y=V;return;}if(k>=V->sz) {x=V;y=NULL;return;}x=V;splaying(x,k);y=x->ch[1]; y->fa=NULL;x->ch[1]=NULL;x->maintain();return;}
}*V,*x,*y;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build_it(V,1,n);while(m--){scanf("%s",s);if(s[2]=='S'){scanf("%d%d",&pos,&tot);for(int i=1;i<=tot;i++) scanf("%d",&a[i]);build_it(x,1,tot);Split(V,pos,V,y);V=Merge(Merge(V,x),y);}else if(s[2]=='L'){scanf("%d%d",&pos,&tot);Split(V,pos-1,V,x);Split(x,tot,x,y);dele(x);V=Merge(V,y);}else if(s[2]=='K'){scanf("%d%d%d",&pos,&tot,&key);Split(V,pos-1,V,x);Split(x,tot,x,y);if(x) x->lz=key;V=Merge(Merge(V,x),y);}else if(s[2]=='V'){scanf("%d%d",&pos,&tot);Split(V,pos-1,V,x);Split(x,tot,x,y);if(x) x->flip^=1;V=Merge(Merge(V,x),y);}else if(s[2]=='T'){scanf("%d%d",&pos,&tot);Split(V,pos-1,V,x);Split(x,tot,x,y);int ans=x?x->sum:0;printf("%d\n",ans);V=Merge(Merge(V,x),y);}else{V->maintain();printf("%d\n",V->ms);}}return 0;
}
这篇关于Splay 模板【NOI2005】 bzoj1500 维修数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
