BZOJ 1500 [NOI2005]维修数列
2017.08.24
题目大意
给你一个序列，请你维护它，支持以下操作：插入元素；删除元素；修改区间种所有元素至同一值；反转区间；求区间和；求区间最大连续子区间和。
这道题Splay可以做qwq
不过这是一道蛇皮的模板题，难度绝对超乎想象qwq 所以就花了很长时间调试qwq
维护区间总和，区间包含左端点的最大区间和，包含右区间的最大区间和，没有特殊条件的最大区间和四个性质。之后Splay就可以有效解决这一问题。
注意这道题压小了运行空间限制，直接开出初始空间+插入总元素空间是不合理的。所以这道题必须要使用内存池解决方案。具体实现方法就是用一个队列表示一下，这样的话不必要开太大就可以解决了，因为占用的空间（树上元素个数总和）比较小。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int son[1200010][2],tot,order[1200010],val[1200010],vall[1200010],valr[1200010],sum[1200010],ori[1200010],inx,iny,inz,root,n,m,fa[1200010],siz[1200010],laz[1200010];
bool rev[1200010];
char mode[1200010];
queue<int>q;
void rever(int pos)
{
swap(son[pos][0],son[pos][1]);
swap(vall[pos],valr[pos]);
rev[pos]^=1;
return;
}
void pushup(int pos)
{
val[pos]=max(max(val[son[pos][0]],val[son[pos][1]]),valr[son[pos][0]]+vall[son[pos][1]]+ori[pos]);
vall[pos]=max(vall[son[pos][0]],sum[son[pos][0]]+ori[pos]+vall[son[pos][1]]);
valr[pos]=max(valr[son[pos][1]],sum[son[pos][1]]+ori[pos]+valr[son[pos][0]]);
siz[pos]=siz[son[pos][0]]+siz[son[pos][1]]+1;
sum[pos]=sum[son[pos][0]]+sum[son[pos][1]]+ori[pos];
return;
}
void pushdown(int pos)
{
int tl=son[pos][0],tr=son[pos][1];
if(laz[pos]!=0xc0c0c0c0)
{
if(tl)
{
ori[tl]=laz[pos];
sum[tl]=laz[pos]*siz[tl];
val[tl]=max(ori[tl],laz[pos]*siz[tl]);
vall[tl]=max(0,laz[pos]*siz[tl]);
valr[tl]=max(0,laz[pos]*siz[tl]);
laz[tl]=laz[pos];
}
if(tr)
{
ori[tr]=laz[pos];
sum[tr]=laz[pos]*siz[tr];
val[tr]=max(ori[tr],laz[pos]*siz[tr]);
vall[tr]=max(0,laz[pos]*siz[tr]);
valr[tr]=max(0,laz[pos]*siz[tr]);
laz[tr]=laz[pos];
}
laz[pos]=0xc0c0c0c0;
}
if(rev[pos])
{
rever(son[pos][0]),rever(son[pos][1]);
rev[pos]=0;
}
}
void rotate(int &k,int x)
{
int y=fa[x],z=fa[y],l=(son[y][1]==x),r=l^1;
if(y==k) k=x;
else son[z][son[z][1]==y]=x;
fa[x]=z,fa[y]=x,fa[son[x][r]]=y,son[y][l]=son[x][r],son[x][r]=y;
pushup(y),pushup(x);
}
void splay(int &k,int x)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if((son[y][0]==x)^(son[z][0]==y)) rotate(k,x);
else rotate(k,y);
}
rotate(k,x);
}
}
int lookfor(int pos,int tx)
{
pushdown(pos);
if(tx<=siz[son[pos][0]]) return lookfor(son[pos][0],tx);
if(tx>siz[son[pos][0]]+1) return lookfor(son[pos][1],tx-siz[son[pos][0]]-1);
return pos;
}
int split(int tx,int ty)
{
tx=lookfor(root,tx),ty=lookfor(root,ty+2);
splay(root,tx),splay(son[root][1],ty);
return son[son[root][1]][0];
}
int build(int l,int r)
{
if(l>r) return 0;
int mid=(l+r)>>1;
son[order[mid]][0]=build(l,mid-1),son[order[mid]][1]=build(mid+1,r);
fa[son[order[mid]][0]]=fa[son[order[mid]][1]]=order[mid];
pushup(order[mid]);
return order[mid];
}
void erase(int tx)
{
if(!tx) return;
erase(son[tx][0]),erase(son[tx][1]),q.push(tx);
son[tx][0]=son[tx][1]=val[tx]=vall[tx]=valr[tx]=ori[tx]=rev[tx]=sum[tx]=fa[tx]=siz[tx]=0;
laz[tx]=0xc0c0c0c0;
}
int main()
{
memset(laz,0xc0,sizeof laz);
scanf("%d%d",&n,&m);
val[0]=0xc0c0c0c0;
for(int i=1;i<=n;++i) scanf("%d",ori+i+1);
tot=n;
n+=2;
for(int i=1;i<=n;++i) order[i]=i;
for(int i=n+1;i<=550000;++i) q.push(i);
root=build(1,n);
while(m--)
{
scanf("%s",mode);
switch(mode[0])
{
case 'I':
{
scanf("%d%d",&inx,&iny);
tot+=iny;
for(int i=1;i<=iny;++i)
{
int id=q.front();
q.pop();
scanf("%d",ori+id);
val[id]=ori[id];
order[i]=id;
}
split(inx+1,inx);
son[son[root][1]][0]=build(1,iny);
fa[son[son[root][1]][0]]=son[root][1];
pushup(son[son[root][1]][0]);
pushup(son[root][1]);
pushup(root);
break;
}
case 'D':
{
scanf("%d%d",&inx,&iny);
tot-=iny;
split(inx,inx+iny-1);
erase(son[son[root][1]][0]);
son[son[root][1]][0]=0;
pushup(son[root][1]);
pushup(root);
break;
}
case 'M':
{
if(mode[2]=='K')
{
scanf("%d%d%d",&inx,&iny,&inz);
int tmp=split(inx,inx+iny-1);
laz[tmp]=inz;
ori[tmp]=inz;
sum[tmp]=inz*siz[tmp];
vall[tmp]=valr[tmp]=max(0,inz*siz[tmp]);
val[tmp]=max(ori[tmp],inz*siz[tmp]);
pushup(son[root][1]);
pushup(root);
}
if(mode[2]=='X')
{
printf("%d\n",val[split(1,tot)]);
}
break;
}
case 'R':
{
scanf("%d%d",&inx,&iny);
rever(split(inx,inx+iny-1));
pushup(son[root][1]);
pushup(root);
break;
}
case 'G':
{
scanf("%d%d",&inx,&iny);
printf("%d\n",sum[split(inx,inx+iny-1)]);
break;
}
}
}
}