请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。
刷完普通平衡树，文艺平衡树板子后，本题纯靠自己想，用了3h打码，4h调试，共7h多终于AC了。
此题我认为堪称“平衡树观止”
题目就是这么地裸。但就是让你写不出来。
粗略地说一下splay题解：
要用到：
1.n+2个点，1，n+2是方便提取用的。
2.哨兵0号点，
3.每个点维护：fa,ch[2],sz,sum,val,lm,rm,ans最后三个是最大子段和用的。
和标记：chan,rev
4.用long long
知识点：
1.区间提取，l-1到根，r+1到根的右儿子。根右儿子的左子树就是操作区间。
2.区间打标记，直接打。
3.找区间左端点，右端点等，返回第k大位置节点编号。
显然不能直接把端点当做编号。因为根本不知道原始编号转到哪里去了。
4.pushdown时机：
pushdown本质是为了将序列保持真正的情况，所以一旦触及，必须pushdown，否则形态一变，子树一换，都完了。
每次查找kth的x，因为每次查找对应一次splay，必须一路上都pushdown，
并且影响的只有rt到x路径上的点，所以其他位置可以不用pushdown
子树内部也是不会动的，不用pushdown。
5.pushup时机：
本质是为了更新信息，所以一个节点变化了，或者其子树变化了，都要pushup
splay里面有，也是路径上改变的点都会pushup的。
另外，操作区间操作后，该子树可能有了变化，还要pushup（根右儿子），pushup（根），别的节点也不会被这次操作影响。
6.1号点和n+2号点。为了不影响答案（可能是负数），所以权值为-inf，并且这两个点一定要保证在区间的两端。
7.0号哨兵
因为我这里是钦定lm，rm，ans都必须选择一个。所以0号的rm，lm，ans都是-inf，才不会因为设成0而取不到负数答案。
8.卡空间（bzoj64MB）
而同一时刻最多500000个。必须垃圾回收，dp[N],dc
操作：
1.插入：直接插成一个链可以，但是之后复杂度并不优秀。
可以分治处理。每次插入mid递归l，mid-1和mid+1，r,数的高度就直接logn了。
开始的加入原数列也是。
对于新加入一些数，先像这样建成一棵树，然后类似区间提取pos，pos+1。
那么，pos+1左儿子就是新树根的fa了，直接嫁接上去。记得pushup（pos+1）与（pos）
见ins，pre函数
2.删除。区间提取、然后直接删除rt的右儿子的左儿子。
要先进入这个子树，放进回收池里。
3.修改。区间提取，直接改。
4.翻转。区间提取。翻转标记。
注意，必须打标记的同时，就要翻转儿子，交换lm，rm
因为虽然是懒标记，但是对于这个节点的影响必须处理。
否则splay时可能会出锅。
因为x左右儿子会有标记，但不翻转，然后rotate(x)会交换子树，pushup(y)就把没有真正正确的x曾经的子树信息记录上去了。
5.区间和。区间提取。直接返回sum
6.最大子段和。直接返回t[rt].ans
注意事项：
1.保护哨兵，保护哨兵，保护哨兵。
2.任何时候，在splay(x)之前，必须确定x路径上的所有点都pushdown了。
3.pushup中，t[x].ans情况较多，不要忘了可以是t[x].val
4.swap(lm,rm)别错了。
#include<bits/stdc++.h>
#define rs t[x].ch[1]
#define ls t[x].ch[0]
#define numb ch-‘0‘
#define ri register int
#define il inline
using namespace std;
typedef long long ll;
const int N=500000+5;
const ll inf=(1LL*1<<61);
char ch;
il void rdint(int &x){
x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch==‘-‘)&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
il void rdll(ll &x){
x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch==‘-‘)&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
struct node{
int ch[2],fa;
ll rm,lm,sum,ans;
int rev;
ll chan;
ll val;
int sz;
void init(int f,ll v){
fa=f,val=v;rm=v;lm=v,ans=v,sum=v;
rev=0,chan=inf;
sz=1;
}
}t[N];
il ll Max(ll a,ll b){
return a>b?a:b;
}
int dc,dp[N],pc;
int n,m,rt;
ll st[N];
il int nc(){
int r=dc?dp[dc--]:++pc;
memset(t+r,0,sizeof (node));return r;
}
il void pushup(int x){
t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].val;
t[x].rm=Max(t[t[x].ch[1]].rm,Max(t[t[x].ch[1]].sum+t[x].val,t[t[x].ch[1]].sum+t[x].val+t[t[x].ch[0]].rm));
t[x].lm=Max(t[t[x].ch[0]].lm,Max(t[t[x].ch[0]].sum+t[x].val,t[t[x].ch[0]].sum+t[x].val+t[t[x].ch[1]].lm));
t[x].ans=Max(t[x].lm,t[x].rm);
t[x].ans=Max(t[x].ans,Max(t[t[x].ch[0]].rm+t[x].val+t[t[x].ch[1]].lm,Max(t[t[x].ch[0]].rm+t[x].val,t[x].val+t[t[x].ch[1]].lm)));
t[x].ans=Max(t[x].ans,Max(t[t[x].ch[0]].ans,t[t[x].ch[1]].ans));
t[x].ans=Max(t[x].ans,t[x].val);//bug 2
t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+1;
}
il void pushdown(int x){
if(t[x].chan!=inf){
if(ls){
t[ls].chan=t[x].chan;
t[ls].val=t[x].chan;
t[ls].sum=t[ls].val*t[ls].sz;
t[ls].rm=t[ls].lm=t[ls].ans=t[ls].val>0?t[ls].sum:t[ls].val;
}
if(rs){
t[rs].chan=t[x].chan;
t[rs].val=t[x].chan;
t[rs].sum=t[rs].val*t[rs].sz;
t[rs].rm=t[rs].lm=t[rs].ans=t[rs].val>0?t[rs].sum:t[rs].val;
}
t[x].chan=inf;
}
if(t[x].rev){
if(ls&&t[ls].val!=-inf){
t[ls].rev^=1;
swap(t[ls].lm,t[ls].rm);//bug1
}
if(rs&&t[rs].val!=-inf){
t[rs].rev^=1;
swap(t[rs].lm,t[rs].rm);//bug1
}
swap(ls,rs);
t[x].rev=0;
}
}
il void rotate(int x){
int y=t[x].fa,d=t[y].ch[1]==x;
t[t[y].ch[d]=t[x].ch[!d]].fa=y;
t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;
t[t[x].ch[!d]=y].fa=x;
pushup(y);
}
il void splay1(int x,int f){
while(t[x].fa!=f){
int y=t[x].fa,z=t[y].fa;
if(z!=f){
rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x);
}
rotate(x);
}
pushup(x);
if(f==0) rt=x;
}
il int kth(int k){
int x=rt;
while(1){
pushdown(x);
int d=k-t[t[x].ch[0]].sz;
if(d<=0) x=t[x].ch[0];
else if(d==1) return x;
else{
k=d-1;
x=t[x].ch[1];
}
}
}
int newrt;
il void splay2(int x,int f){
while(t[x].fa!=f){
int y=t[x].fa,z=t[y].fa;
if(z!=f){
rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x);
}
rotate(x);
}
pushup(x);
if(f==0) newrt=x;
}
il void build(ll v){
if(!newrt){
newrt=nc();
t[newrt].init(0,v);
return;
}
int x=newrt;
while(1){
if(!t[x].ch[1]){
t[x].ch[1]=nc();
t[t[x].ch[1]].init(x,v);
x=t[x].ch[1];
break;
}
x=t[x].ch[1];
}
splay2(x,0);
}
il int pre(int l,int r,int f){
if(l>r){
return 0;
}
int mid=(l+r)>>1;
int x=nc();
t[x].init(f,st[mid]);
t[x].ch[0]=pre(l,mid-1,x);
t[x].ch[1]=pre(mid+1,r,x);
pushup(x);
return x;
}
il void ins(int pos,int tot){
newrt=0;
for(ri i=1;i<=tot;i++){
rdll(st[i]);
}
newrt=pre(1,tot,0);
int x=kth(pos+1);
int y=kth(pos+2);
splay1(x,0);
splay1(y,x);
t[y].ch[0]=newrt;
t[newrt].fa=y;
pushup(y);
pushup(x);
}
il void del(int x){
if(t[x].ch[0]) del(t[x].ch[0]);
dp[++dc]=x;
if(t[x].ch[1]) del(t[x].ch[1]);
}
il void remove(int pos,int tot){
int l=kth(pos);
int r=kth(pos+tot+1);
splay1(l,0);
splay1(r,l);
del(t[r].ch[0]);
t[r].ch[0]=0;
pushup(r);
pushup(l);
}
il void upda(int pos,int tot,ll c){
int l=kth(pos);
int r=kth(pos+tot+1);
splay1(l,0);
splay1(r,l);
int x=t[r].ch[0];
t[x].chan=c;
t[x].val=c;
t[x].sum=t[x].val*t[x].sz;
t[x].rm=t[x].lm=t[x].ans=t[x].val>0?t[x].sum:t[x].val;
pushup(r);
pushup(l);
}
il void reverse(int pos,int tot){
int l=kth(pos);
int r=kth(pos+tot+1);
splay1(l,0);
splay1(r,l);
int x=t[r].ch[0];
t[x].rev^=1;
swap(t[x].lm,t[x].rm);
pushup(r);
pushup(l);
}
il ll qs(int pos,int tot){
int l=kth(pos);
int r=kth(pos+tot+1);
splay1(l,0);
splay1(r,l);
int x=t[r].ch[0];
int ret=t[x].sum;
pushdown(x);//bug 3
splay1(x,0);
return ret;
}
int main()
{
t[0].lm=t[0].rm=t[0].ans=-inf;//warning warning warning !!!
t[0].sz=0;t[0].sum=0;
scanf("%d%d",&n,&m);
st[1]=-inf;
for(int i=2;i<=n+1;i++){
rdll(st[i]);
}
st[n+2]=-inf;
rt=pre(1,n+2,0);
char lp[20];
int pos,tot;
ll c;
int cnt=0;
for(ri i=1;i<=m;i++){
ch=getchar();
while(ch>‘Z‘||ch<‘A‘)ch=getchar();
for(cnt=0;(ch==‘-‘)||(ch<=‘Z‘&&ch>=‘A‘);ch=getchar())lp[++cnt]=ch;
if(lp[1]==‘I‘){
rdint(pos),rdint(tot);
if(tot==0) continue;
ins(pos,tot);
}
else if(lp[1]==‘D‘){
rdint(pos),rdint(tot);
if(tot==0) continue;
remove(pos,tot);
}
else if(lp[1]==‘M‘&&lp[3]==‘K‘){
rdint(pos),rdint(tot);rdll(c);
if(tot==0) continue;
upda(pos,tot,c);
}
else if(lp[1]==‘M‘&&lp[3]==‘X‘){
printf("%lld\n",t[rt].ans);
}
else if(lp[1]==‘G‘){
rdint(pos),rdint(tot);
if(tot==0) printf("0\n");
else printf("%lld\n",qs(pos,tot));
}
else if(lp[1]==‘R‘){
rdint(pos),rdint(tot);
if(tot==0) continue;
reverse(pos,tot);
}
}
return 0;
}
原文：https://www.cnblogs.com/Miracevin/p/9643977.html