题解 P2042 【[NOI2005]维护数列】
本蒟蒻写的第一道平衡树大题，发个题解纪念一下。
前言：
本蒟蒻使用的是fhq_treap，相对来说可能会短一点(但是由于我太菜了所以看起来还是很长）
本篇题解实现参考了 @x义x 大佬的代码（窝太菜了自己写不出）
正题:
看题：惊人的时间限制——1s，于是可以先做一手卡常的准备了。再看空间上的限制和本题目中那一堆操作，想都不用想就知道肯定要维护一大堆东西，4e6的数据范围128MB开得下我觉得比较难，题目又保证了同一时间内节点数小于等于5e5，所以节点回收是肯定的。然后我们开始一步步解决这个题目。 先把节点定义放出来：
struct Node
{
int lson,rson,siz,val,cov,rnd; //cov为区间覆盖操作所要使用的值
int lazy_rev,lazy_cov; //这两个标记很显然吧emmm...
int sum,pre_mx,suc_mx,all_mx; //前缀最大值，后缀最大值，总最大值，和
}t[MAXN];int rt;
#define ls(x) t[x].lson //宏定义——偷懒专用
#define rs(x) t[x].rson一、如何回收节点？
考虑开一个栈来存没有用的节点，删除节点的时候就把那些被删的节点堆进去就行，在代码里有清楚的体现
二、如何维护答案？
对于最大子段和的维护考虑维护一个前缀最大和，后缀最大和 和 自身这棵树内的最大和，如何合并呢？
inline void Update(int x)
{
if(!x) return ;
t[x].siz=t[ls(x)].siz+t[rs(x)].siz+1;
t[x].sum=t[ls(x)].sum+t[rs(x)].sum+t[x].val;
t[x].pre_mx=max(t[ls(x)].pre_mx,t[ls(x)].sum+t[x].val+t[rs(x)].pre_mx,0);
t[x].suc_mx=max(t[rs(x)].suc_mx,t[rs(x)].sum+t[x].val+t[ls(x)].suc_mx,0);
t[x].all_mx=max(t[x].val,t[x].val+t[ls(x)].suc_mx+t[rs(x)].pre_mx);
if(ls(x)) t[x].all_mx=max(t[x].all_mx,t[ls(x)].all_mx);
if(rs(x)) t[x].all_mx=max(t[x].all_mx,t[rs(x)].all_mx);
}就这个样子。因为前缀后缀都是可以不取的所以可以为0，但是自身不能取0，因为题目强制必须取一个(有毒.....)
三、如何下放标记？
是不是fhq_treap的题目都只要在split的时候丢标记啊......
(反正它过了）
四、这份代码有锅吗，可以抄吗
显然你是可以抄的
但是这个代码有一个很神奇事情就是开不了O2，一开O2就RE，有没有哪位大佬告诉我这是为啥呀5555.
Orz Orz Orz
五、关于代码里的max
我比较懒，就重载了一个三个参数的max
六、code
#include <cstdio>
#define R register
const int MAXN=5e5+10;
const int RAND_1=1e9+7;
const int RAND_2=1e9+9;
inline int read()
{
char a=getchar();int x=0,f=1;
for(;a>'9'||a<'0';a=getchar()) if(a=='-') f=-1;
for(;a>='0'&&a<='9';a=getchar()) x=x*10+a-'0';
return x*f;
}
int Seed='L'+'C'+'N'+'B'+171098569;
inline int swap(int &x,int &y) { x^=y;y^=x;x^=y; }
inline int max(int x,int y) { return x>y?x:y;}
inline int max(int x,int y,int z) { return max(x,max(y,z)); }
inline int rand() { return Seed=(Seed*RAND_1+0x7f7f7f7f)*RAND_2*Seed; }
int n,m;
int stk[MAXN],cnt;
struct Node
{
int lson,rson,siz,val,cov,rnd;
int lazy_rev,lazy_cov;
int sum,pre_mx,suc_mx,all_mx;
}t[MAXN];int rt;
#define ls(x) t[x].lson
#define rs(x) t[x].rson
inline int New(int k)
{
int x=stk[cnt--];
ls(x)=rs(x)=t[x].cov=t[x].lazy_rev=t[x].lazy_cov=0;
t[x].siz=1;
t[x].val=t[x].sum=k;
t[x].pre_mx=t[x].suc_mx=max(0,k);
t[x].all_mx=k;
t[x].rnd=rand();
return x;
}
inline void Update(int x)
{
if(!x) return ;
t[x].siz=t[ls(x)].siz+t[rs(x)].siz+1;
t[x].sum=t[ls(x)].sum+t[rs(x)].sum+t[x].val;
t[x].pre_mx=max(t[ls(x)].pre_mx,t[ls(x)].sum+t[x].val+t[rs(x)].pre_mx,0);
t[x].suc_mx=max(t[rs(x)].suc_mx,t[rs(x)].sum+t[x].val+t[ls(x)].suc_mx,0);
t[x].all_mx=max(t[x].val,t[x].val+t[ls(x)].suc_mx+t[rs(x)].pre_mx);
if(ls(x)) t[x].all_mx=max(t[x].all_mx,t[ls(x)].all_mx);
if(rs(x)) t[x].all_mx=max(t[x].all_mx,t[rs(x)].all_mx);
}
inline void Reverse(int x)
{
if(!x) return ;
swap(ls(x),rs(x));
swap(t[x].pre_mx,t[x].suc_mx);
t[x].lazy_rev^=1;
}
inline void Cover(int x,int col)
{
t[x].val=t[x].cov=col;
t[x].sum=t[x].siz*col;
t[x].pre_mx=t[x].suc_mx=max(0,t[x].sum);
t[x].all_mx=max(col,t[x].sum);
t[x].lazy_cov=1;
}
inline void Pushdown(int x)
{
if(!x) return ;
if(t[x].lazy_rev)
{
if(ls(x)) Reverse(ls(x));
if(rs(x)) Reverse(rs(x));
t[x].lazy_rev=0;
}
if(t[x].lazy_cov)
{
if(ls(x)) Cover(ls(x),t[x].cov);
if(rs(x)) Cover(rs(x),t[x].cov);
t[x].lazy_cov=t[x].cov=0;
}
}
inline void Delete(int x)
{
if(!x) return;
stk[++cnt]=x;
if(ls(x)) Delete(ls(x));
if(rs(x)) Delete(rs(x));
}
inline void Split(int now,int k,int &x,int &y)
{
if(!now) { x = y = 0; return ; }
Pushdown(now);
if(t[ls(now)].siz+1<=k)
{
x=now;
Split(rs(now),k-t[ls(now)].siz-1,rs(now),y);
}
else
{
y=now;
Split(ls(now),k,x,ls(now));
}
Update(now);
}
inline int Merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].rnd<t[y].rnd)
{
Pushdown(x);
rs(x)=Merge(rs(x),y);
Update(x); return x;
}
else
{
Pushdown(y);
ls(y)=Merge(x,ls(y));
Update(y); return y;
}
}
int array[MAXN];
inline int Build(int l,int r)
{
if(l==r) return New(array[l]);
int mid=l+r;mid>>=1;
return Merge(Build(l,mid),Build(mid+1,r));
}
char opt[10];
int main()
{
n=read();m=read();
for(R int i=1;i<MAXN;i++) stk[++cnt]=i;
for(R int i=1;i<=n;i++) array[i]=read();
rt=Build(1,n);
while(m--)
{
scanf("%s",opt);
if(opt[0]=='I')
{
int pos=read(),tot=read();
int x,y;
Split(rt,pos,x,y);
for(R int i=1;i<=tot;i++) array[i]=read();
x=Merge(x,Build(1,tot));
rt=Merge(x,y);
}
if(opt[0]=='D')
{
int pos=read(),tot=read();
int x,y,z;
Split(rt,pos-1,x,y);
Split(y,tot,y,z);
Delete(y);
rt=Merge(x,z);
}
if(opt[2]=='K')
{
int pos=read(),tot=read(),col=read();
int x,y,z;
Split(rt,pos-1,x,y);
Split(y,tot,y,z);
Cover(y,col);
rt=Merge(Merge(x,y),z);
}
if(opt[0]=='R')
{
int pos=read(),tot=read();
int x,y,z;
Split(rt,pos-1,x,y);
Split(y,tot,y,z);
Reverse(y);
rt=Merge(Merge(x,y),z);
}
if(opt[0]=='G')
{
int pos=read(),tot=read();
int x,y,z;
Split(rt,pos-1,x,y);
Split(y,tot,y,z);
printf("%d\n",t[y].sum);
rt=Merge(Merge(x,y),z);
}
if(opt[2]=='X')
{
printf("%d\n",t[rt].all_mx);
}
}
return 0;
}