【BZOJ1500】[NOI2005]維修數列 Splay

【BZOJ1500】[NOI2005]維修數列

Description

Input

輸入的第1 行包含兩個數N 和M(M ≤20 000)，N 表示初始時數列中數的個數，M表示要進行的操作數目。
第2行包含N個數字，描述初始時的數列。
以下M行，每行一條命令，格式參見問題描述中的表格。
任何時刻數列中最多含有500 000個數，數列中任何一個數字均在[-1 000, 1 000]內。
插入的數字總數不超過4 000 000個，輸入文件大小不超過20MBytes。

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

題解：裸的Splay，只不過全是細節，我還是不夠細啊~

*要開滾動數組記錄有哪些空余的位置，防止MLE（但實測600000的數組就行）

*INSERT：直接一個一個往里加就行，加成一條鏈也無所謂，不會TLE

*DELETE：因為要釋放空間，所以必須一個一個刪除，遞歸即可

*MAKE_SAME：沒啥說的
*REVERSE：最好是先修改，再給兒子打標記（也就是說標記只對兒子起作用），這樣比較清晰

*GET_SUM：沒啥說的
*MAX_SUM：巨惡心的pushup和pushdown，看代碼就知道了

?

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
struct point
{int ch[2],fa,siz,tag,v,sv,sm,ls,rs,re;
}s[600010];
int n,m,root;
int num[500010];
char str[20];
queue<int> q;
void pushdown(int x)
{if(s[x].re){swap(s[s[x].ch[0]].ch[0],s[s[x].ch[0]].ch[1]);swap(s[s[x].ch[1]].ch[0],s[s[x].ch[1]].ch[1]);swap(s[s[x].ch[0]].ls,s[s[x].ch[0]].rs);swap(s[s[x].ch[1]].ls,s[s[x].ch[1]].rs);if(s[x].ch[0])	s[s[x].ch[0]].re^=1;if(s[x].ch[1])	s[s[x].ch[1]].re^=1;s[x].re=0;}if(s[x].tag!=1<<30){if(s[x].ch[0]){s[s[x].ch[0]].v=s[s[x].ch[0]].tag=s[x].tag;s[s[x].ch[0]].sv=s[x].tag*s[s[x].ch[0]].siz;s[s[x].ch[0]].ls=s[s[x].ch[0]].rs=max(s[s[x].ch[0]].sv,0);s[s[x].ch[0]].sm=max(s[s[x].ch[0]].sv,s[x].tag);}if(s[x].ch[1]){s[s[x].ch[1]].v=s[s[x].ch[1]].tag=s[x].tag;s[s[x].ch[1]].sv=s[x].tag*s[s[x].ch[1]].siz;s[s[x].ch[1]].ls=s[s[x].ch[1]].rs=max(s[s[x].ch[1]].sv,0);s[s[x].ch[1]].sm=max(s[s[x].ch[1]].sv,s[x].tag);}s[x].tag=1<<30;}
}
void pushup(int x)
{s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;s[x].ls=max(s[s[x].ch[0]].ls,s[s[x].ch[0]].sv+s[x].v+s[s[x].ch[1]].ls);s[x].rs=max(s[s[x].ch[1]].rs,s[s[x].ch[1]].sv+s[x].v+s[s[x].ch[0]].rs);s[x].sm=max(s[s[x].ch[0]].rs+s[x].v+s[s[x].ch[1]].ls,max(s[s[x].ch[0]].sm,s[s[x].ch[1]].sm));s[x].sv=s[s[x].ch[0]].sv+s[x].v+s[s[x].ch[1]].sv;
}
int readin()
{int ret=0,f=1;	char gc=getchar();while(gc<'0'||gc>'9'){if(gc=='-')f=-f;	gc=getchar();}while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();return ret*f;
}
int rotate(int x,int &k)
{int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);if(z)	s[z].ch[y==s[z].ch[1]]=x;if(y==k)	k=x;s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;s[x].ch[d^1]=y;pushup(y),pushup(x);
}
void splay(int x,int &k)
{while(x!=k){int y=s[x].fa,z=s[y].fa;if(y!=k){if((x==s[y].ch[1])^(y==s[z].ch[1]))	rotate(x,k);else	rotate(y,k);}rotate(x,k);}
}
void build(int l,int r,int last)
{if(l>r)	return ;int mid=l+r>>1;s[mid].fa=last,s[last].ch[mid>last]=mid;s[mid].v=num[mid];s[mid].tag=1<<30;build(l,mid-1,mid),build(mid+1,r,mid);pushup(mid);
}
int find(int x,int y)
{pushdown(x);if(s[s[x].ch[0]].siz+1==y)	return x;if(y<=s[s[x].ch[0]].siz)	return find(s[x].ch[0],y);return find(s[x].ch[1],y-s[s[x].ch[0]].siz-1);
}
void del(int &x)
{if(!x) return;q.push(x);del(s[x].ch[0]),del(s[x].ch[1]);x=0;
}
int main()
{n=readin(),m=readin();int i,j,a,b,c,t,u;s[0].sm=num[1]=num[n+2]=-1<<30;for(i=1;i<=n;i++)	num[i+1]=readin();n+=2,root=(n+1)/2;build(1,root-1,root),build(root+1,n,root);s[root].v=num[root];s[root].tag=1<<30;pushup(root);for(i=n+1;i<=600000;i++)	q.push(i);for(i=1;i<=m;i++){scanf("%s",str);switch(str[2]){case 'S':{a=readin()+1,b=readin();splay(find(root,a+1),root),splay(find(root,a),s[root].ch[0]);t=s[root].ch[0];for(j=1;j<=b;j++){c=readin();u=q.front(),q.pop();s[u].v=c;s[t].ch[1]=u,s[u].fa=t;s[u].re=0,s[u].tag=1<<30;t=u;}while(t!=root){pushup(t);t=s[t].fa;}break;}case 'L':{a=readin()+1,b=readin();splay(find(root,a-1),root),splay(find(root,a+b),s[root].ch[1]);del(s[s[root].ch[1]].ch[0]);pushup(s[root].ch[1]);break;}case 'K':{a=readin()+1,b=readin();splay(find(root,a-1),root),splay(find(root,a+b),s[root].ch[1]);c=s[s[root].ch[1]].ch[0];s[c].v=s[c].tag=readin();s[c].re=0;s[c].sv=s[c].siz*s[c].v;s[c].ls=s[c].rs=max(s[c].sv,0);s[c].sm=max(s[c].sv,s[c].v);break;}case 'V':{a=readin()+1,b=readin();splay(find(root,a-1),root),splay(find(root,a+b),s[root].ch[1]);c=s[s[root].ch[1]].ch[0];swap(s[c].ch[0],s[c].ch[1]);swap(s[c].ls,s[c].rs);s[c].re=1;break;}case 'T':{a=readin()+1,b=readin();splay(find(root,a-1),root),splay(find(root,a+b),s[root].ch[1]);printf("%d\n",s[s[s[root].ch[1]].ch[0]].sv);break;}case 'X':{printf("%d\n",s[root].sm);break;}}}return 0;
}

?