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; }