P2042 [NOI2005] 维护数列
坑点：
- 空间问题，要把删除了的节点循环利用
- 修改操作的值可能为0
- 时间问题，insert时直接把数列build(l,r)，然后合并
- 最大子段和，
改了好几遍，每次以为改好了，结果后面又发现错误了，不能为空 - 修改操作，会让max1和max2颠倒
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=5e5+5;
int tot,root,a,b,c,n,m,q,cnt,sq[N];
int ls[N],rs[N],dat[N],val[N],tag[N];
bool laz[N],falg[N];
int siz[N],sum[N],max0[N],max1[N],maxn[N],w[N];//0->l,1->r
int New(int k){
int id=(cnt)?sq[cnt--]:++tot;
val[id]=sum[id]=maxn[id]=k;
ls[id]=rs[id]=tag[id]=laz[id]=falg[id]=0;
max0[id]=max1[id]=max(0,k);
siz[id]=1;dat[id]=rand();
return id;
}
void updat(int p){
if(!p)return ;
siz[p]=siz[ls[p]]+siz[rs[p]]+1;
sum[p]=sum[ls[p]]+sum[rs[p]]+val[p];
max0[p]=max(0,max(max0[ls[p]],max0[rs[p]]+val[p]+sum[ls[p]]));
max1[p]=max(0,max(max1[rs[p]],max1[ls[p]]+val[p]+sum[rs[p]]));
maxn[p]=max(0,max1[ls[p]]+max0[rs[p]])+val[p];
if(ls[p])maxn[p]=max(maxn[p],maxn[ls[p]]);
if(rs[p])maxn[p]=max(maxn[p],maxn[rs[p]]);
}
void rever(int p){
swap(ls[p],rs[p]);
swap(max0[p],max1[p]);
laz[p]^=1;
}
void cover(int p,int x){
tag[p]=val[p]=x;
sum[p]=siz[p]*x;
maxn[p]=max(x,sum[p]);
max0[p]=max1[p]=max(0,sum[p]);
falg[p]=1;
}
void pushdown(int p){
if(laz[p]){
if(ls[p])rever(ls[p]);
if(rs[p])rever(rs[p]);
laz[p]=0;
}
if(falg[p]){
if(ls[p])cover(ls[p],tag[p]);
if(rs[p])cover(rs[p],tag[p]);
tag[p]=falg[p]=0;
}
}
void split(int p,int k,int &x,int &y){
if(!p){
x=y=0;return ;
}
pushdown(p);
if(siz[ls[p]]<k){
x=p;
split(rs[p],k-siz[ls[p]]-1,rs[p],y);
}
else{
y=p;split(ls[p],k,x,ls[p]);
}
updat(p);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(dat[x]>dat[y]){
pushdown(x);
rs[x]=merge(rs[x],y);
updat(x);
return x;
}
else
{
pushdown(y);
ls[y]=merge(x,ls[y]);
updat(y);
return y;
}
}
void cun(int p){
if(!p)return ;
sq[++cnt]=p;
if(ls[p])cun(ls[p]);
if(rs[p])cun(rs[p]);
}
void insert(int k,int x){
split(root,k,a,b);
root=merge(merge(a,New(x)),b);
}
int build(int l,int r){
if(l==r)return New(w[l]);
int mid=(l+r)>>1;
int x=merge(build(l,mid),build(mid+1,r));
return x;
}
int main(){
// freopen("P2042_2.in","r",stdin);
// freopen("1.out","w",stdout);
n=read(),m=read();
int x,y,z;string s;
for(int i=1;i<=n;i++)w[i]=read();
root=build(1,n);
for(int i=1;i<=m;i++){
cin>>s;
if(s[0]=='I'){
x=read(),y=read();
for(int j=1;j<=y;j++)w[j]=read();
split(root,x,a,b);
root=merge(merge(a,build(1,y)),b);
}
else if(s[0]=='D'){
x=read(),y=read();
split(root,x-1,a,b);
split(b,y,b,c);
cun(b);
root=merge(a,c);
}
else if(s[0]=='M'&&s[2]=='K'){
x=read(),y=read(),z=read();
split(root,x-1,a,b);
split(b,y,b,c);
cover(b,z);
root=merge(merge(a,b),c);
}
else if(s[0]=='R'){
x=read(),y=read();
split(root,x-1,a,b);
split(b,y,b,c);
rever(b);
root=merge(a,merge(b,c));
}
else if(s[0]=='G'){
x=read(),y=read();
split(root,x-1,a,b);
split(b,y,b,c);
printf("%d\n",sum[b]);
root=merge(merge(a,b),c);
}
else{
printf("%d\n",maxn[root]);
}
}
return 0;
}