1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 6366 Solved: 1910
[ Submit][ Status]
Description
Input
输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
HINT
题意：RT
思路：比较好的splay模板题，基本上这题过了，splay的基本操作也就掌握的差不多了，包括向下更新，翻转，这里我在整个序列上增加了两个节点，一端一个，这样可以方便
区间操作，A完这题感觉整个人都傻逼了，其实代码能力怎么样一写这种代码长的题目就检测出来了，感觉要提高代码能力要经常写这些代码老长老长的题~
这里讲一讲怎样用splay提取一段区间，新手看看吧，大神可以一笑而过~~
假设splay所维护的整个区间长度为n，实际长度为n+2，因为开始的时候在左端设置了0节点，在右端设置了n+1节点，设置这两个节点是为了方便区间的提取操作
假设要提取区间[L，R]，可以先将第L-1个节点旋转到根，然后再将第R+1个节点旋转到第L-1个节点的下面，现在第R+1个节点的左孩子所覆盖的区间就是[L，R]，怎么
样，是不是很简单了，其实我觉得splay的关键操作就三个，1.将j节点旋转到i节点的下面，2.旋转操作，3.区间提取，然后其它的操作像什么push up，push down就
类似于线段树了~
有了区间提取操作做基础以后，现在可以任意插入一段区间，任意删除一段区间，求任意区间的信息（和，最大值等等）
1.在pos位置后面插入一段区间，先将第pos节点旋转到根，再将第pos+1节点旋转到pos节点的下面，现在第pos+1节点一定没有左子树，然后将要插入的区间作为其左
子树，这里可以将要插入的区间先建成一棵平衡树再插入，效率会高一点
2.将[L，R]区间删除，先将第L-1节点旋转到根，再将第R+1节点旋转到L-1节点的下面，然后将R+1节点的左子树赋为null即可
3.查询区间的信息也一样
4.有一点要注意的是，在对整棵splay做修改之后要及时的从修改的地方旋转到根，这就类似于线段树在修改任意一段区间以后要及时的push up操作
难点基本都已攻破，细节看代码，包括push down，push up ，旋转，splay，翻转，得到第k大的节点，得到一段区间等等~
#include
#include
#include
#include
using namespace std;
#define maxn 600010
#define INF (~0U>>1)
int maxi(int x,int y)
{
return x>y?x:y;
}
struct node{
int v;
int sum;
int pre;
int suf;
int mx;
int co;
int rev;
int sz;
node *p;
node *ch[2];
node(){
sz=rev=co=sum=0;
pre=suf=v=mx=-1000000000;
p=ch[0]=ch[1]=this;
}
int cd(node *o)
{
return ch[1]==o?1:0;
}
void addc(node *o,int d)
{
ch[d]=o;
o->p=this;
}
void pd(int c)
{
sum=c*sz;
pre=suf=mx=maxi(sum,c);
v=c;
co=1;
}
void revv()
{
rev^=1;
swap(ch[0],ch[1]);
swap(pre,suf);
}
}Tnull,*null=&Tnull;
node *newnode(int v)
{
node *u=(node*)malloc(sizeof(node));
u->sz=1;
u->mx=u->v=u->sum=u->pre=u->suf=v;
u->co=u->rev=0;
return u;
}
void pushdown(node *o)
{
if(o->co){
for(int i=0;i<2;++i)if(o->ch[i]!=null)o->ch[i]->pd(o->v);
o->co=0;
}
if(o->rev){
for(int i=0;i<2;++i)if(o->ch[i]!=null)o->ch[i]->revv();
o->rev=0;
}
}
void pushup(node *o)
{
o->sz=o->ch[0]->sz+o->ch[1]->sz+1;
o->sum=o->ch[0]->sum+o->ch[1]->sum+o->v;
o->pre=maxi( o->ch[0]->sum+o->v+o->ch[1]->pre,maxi( o->ch[0]->pre, o->ch[0]->sum+o->v) );
o->suf=maxi( o->ch[1]->sum+o->v+o->ch[0]->suf,maxi( o->ch[1]->suf, o->ch[1]->sum+o->v) );
o->mx=maxi( o->v ,maxi(o->ch[0]->mx,o->ch[1]->mx) );
o->mx=maxi( o->mx, maxi(o->ch[0]->suf+o->v , o->ch[1]->pre+o->v ) );
o->mx=maxi( o->mx, o->ch[0]->suf+o->v+o->ch[1]->pre );
}
void rot(node *o)
{
node *k=o->p;
int d=k->cd(o);
pushdown(k);
pushdown(o);
k->addc(o->ch[d^1],d);
k->p->addc(o,k->p->cd(k));
o->addc(k,d^1);
pushup(k);
}
void splay(node *o,node *goal)
{
while(o->p!=goal)
{
if(o->p->p==goal)rot(o);
else o->p->p->cd(o->p)==o->p->cd(o) ? (rot(o->p),rot(o)) : (rot(o),rot(o));
}
pushup(o);
}
int a[maxn];
node *build(int l,int r)
{
if(l>r)return null;
int m=l+r>>1;
node *o=newnode(a[m]);
o->addc(build(l,m-1),0);
o->addc(build(m+1,r),1);
pushup(o);
return o;
}
node *select(int k)
{
for(node *o=null->ch[1];;)
{
pushdown(o);
int c=o->ch[0]->sz;
if(c==k)return o;
if(c>k)o=o->ch[0];
else {
o=o->ch[1];
k-=c+1;
}
}
}
node *getnode(int l,int r)
{
node *t1=select(l-1);
node *t2=select(r+1);
splay(t1,null);
splay(t2,t1);
return t2->ch[0];
}
void *addnode(int p,node *o)
{
node *t1=select(p);
node *t2=select(p+1);
splay(t1,null);
splay(t2,t1);
t2->addc(o,0);
splay(o,null);
}
void Free(node *o)
{
if(o==null)return;
Free(o->ch[0]);
Free(o->ch[1]);
free(o);
}
char s[20];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i;
for(i=1;i<=n;++i)scanf("%d",&a[i]);
a[0]=a[n+1]=-1;
null->addc(build(0,n+1),1);
for(i=0;i
p->ch[0]=null; splay(k->p,null); Free(k); } else if(s[2]=='K'){ scanf("%d%d%d",&pos,&tot,&v); node *k=getnode(pos,pos+tot-1); k->pd(v); splay(k,null); } else if(s[0]=='R'&&s[1]=='E'){ scanf("%d%d",&pos,&tot); node *k=getnode(pos,pos+tot-1); k->revv(); splay(k,null); } else if(s[0]=='G'){ scanf("%d%d",&pos,&tot); node *k=getnode(pos,pos+tot-1); printf("%d\n",k->sum); } else { node *k=getnode(1,null->ch[1]->sz-2); printf("%d\n",k->mx); } } Free(null->ch[1]); null->ch[1]=null; } return 0; }