并不对劲的bzoj1500: [NOI2005]维修数列

阅读原文时间：2023年07月11日阅读：1

传送门->

这题没什么好说的……小清新数据结构题……并不对劲的人太菜了，之前照着标程逐行比对才过了这道题，前几天刚刚把这题一遍写对……

其实这题应该口胡很容易。操作1，2，3，4，5就是普通的splay支持的那些操作。操作6要转一个小弯，对于每个点记lmax,rmax,xmax，分别表示贴左边界的最大连续子段和（可能为空）、贴右边界的最大连续子段和（可能为空）、最大子段和（不能为空）。现在考虑将lson[u]和rson[u]子树对应的序列的lmax,rmax,xmax经过一些神奇的操作合并，得到u的子树对应的这些值。lmax[u]：跨越u时是左边整段+key[u]+右边lmax；不跨越时是左边的lmax。rmax[u]：同上。xmax[u]：跨越u时是左边贴右边界+右边贴左边界+key[u]；不跨越时左边、右边的xmax二选一。

听上去这题已经口胡完了，但是调它的路还长这呢。要注意几点小小的问题：

1.一开始建树时不要一个个插入，可以每次取中点作为根，再递归处理左右两边，这样会形成更加平衡的树。会发现操作1是插入一个序列，可以类似地先将这个序列建成平衡的树。（不这么做可能TLE）

2.发现数据略坑，无脑新建点会需要4*10^6个点。但是只会有5*10^5个点被用到，所以对于那些删掉的点，可以将它们的编号存在【随便什么简单数据结构】里，用的时候再拿出来。（不这么做会MLE或RE）

3.在做2时，假设将编号x存到了【随便什么简单数据结构】里，发现它被删除前的父亲、儿子、lmax、rmax等一系列信息还在，注意要记得初始化。（不这么做当然会WA）

4.在pushdown时，发现当有一段被改成同一个数后就不用管翻转标记了。（不这么做会常数极大）

5.pushup/down时懒得判某个儿子为0怎么办？在pushup/down前后强行将编号为0的点的各种值全部设置为初始值！（不这么做会写烦）

6.在做5时，xmax[0]=-inf,其余都为0。（不这么做会WA）

7.对于某点打上修改标记时，pushdown前它的左、右儿子都没有改变，这时pushup就会得到修改前的答案。不能盲目地pushup。（不这么做会WA）

8.pushdown翻转标记时，记得交换lmax,rmax。（不这么做会WA）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,x,y) for(register LL i=(x);i<=(y);i++) #define dwn(i,x,y) for(register LL i=(x);i>=(y);i--)
#define re register
#define Int re LL
#define maxn 500010
#define mi (l+r>>1)
#define ls son[u][0]
#define rs son[u][1]
#define s0 fa[0]=son[0][0]=son[0][1]=rev[0]=sum[0]=siz[0]=key[0]=lm[0]=rm[0]=yes[0]=0,xm[0]=-inf[0]
#define rks son[rk][0]
#define LL long long
using namespace std;
inline LL read()
{
LL x=0,f=1;
char ch=getchar();
while(isdigit(ch)==0 && ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(LL x)
{
LL f=0;char ch[20];
if(!x){puts("0");return;}
if(x<0){putchar('-');x=-x;} while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n'); } LL n,m; LL fa[maxn],son[maxn][2],rev[maxn],sum[maxn],xm[maxn],siz[maxn],inf[5],x,y,cnt; LL st[maxn],top,tmp[maxn],key[maxn],rt,lm[maxn],rm[maxn],yes[maxn]; void mark(LL u,LL k){if(u)yes[u]=1ll,key[u]=k,sum[u]=k*siz[u],xm[u]=max(k*siz[u],k),lm[u]=rm[u]=max(k*siz[u],0ll);} void rever(LL u){if(u)rev[u]^=1ll,swap(ls,rs),swap(lm[u],rm[u]); } void pu(LL u) { s0; siz[u]=siz[ls]+siz[rs]+1ll; sum[u]=sum[ls]+sum[rs]+key[u]; lm[u]=max(lm[ls],sum[ls]+key[u]+lm[rs]); rm[u]=max(rm[rs],sum[rs]+key[u]+rm[ls]); xm[u]=max(max(xm[ls],xm[rs]),lm[rs]+rm[ls]+key[u]); s0; } void pd(LL u) { s0; if(yes[u])mark(ls,key[u]),mark(rs,key[u]),rev[u]=yes[u]=0; else if(rev[u])rever(ls),rever(rs),rev[u]=0; s0; } LL res(LL k,LL f) { LL u; if(top>0ll)u=st[top--];
else u=++cnt;
fa[u]=f,ls=rs=rev[u]=yes[u]=0;siz[u]=1;
sum[u]=xm[u]=k;key[u]=k;
lm[u]=rm[u]=max(0ll,k);
return u;
}
LL build(LL l,LL r)
{
if(l>r)return 0;
LL u=res(tmp[mi],0ll);
ls=build(l,mi-1ll),rs=build(mi+1ll,r);
fa[ls]=fa[rs]=u,pu(u);
return u;
}
LL kth(LL k)
{
LL u=rt;
while(u)
{
pd(u);
LL rk=siz[ls]+1ll;
if(rk==k)break;
if(rk>k)u=ls;
else k-=rk,u=rs;
}
return u;
}
void getst(LL u)
{
if(!u)return ;
pd(u),getst(ls),st[++top]=u,getst(rs);
}
inline LL getso(LL u) {return son[fa[u]][0]!=u;}
void rot(LL u)
{
LL fu=fa[u],ffu=fa[fu],l=getso(u),fl=getso(fu),r=l^1ll,rson=son[u][r];
fa[fu]=u,fa[u]=ffu,fa[rson]=fu,son[ffu][fl]=u,son[fu][l]=rson,son[u][r]=fu;
pu(fu),pu(u);
}
void splay(LL u,LL k)
{
while(fa[u]!=k){LL fu=fa[u];if(fa[fu]!=k)rot(getso(u)^getso(fu)?u:fu);rot(u);}
if(!k)rt=u;
}
void ins(LL pos,LL num)
{
LL lk=kth(pos),rk=kth(pos+1ll);
splay(lk,0),splay(rk,lk);
rep(i,1,num)tmp[i]=read();
rks=build(1,num),fa[rks]=rk,pu(rk),pu(lk);
}
void del(LL pos,LL num)
{
LL lk=kth(pos-1ll),rk=kth(pos+num);
splay(lk,0),splay(rk,lk),getst(rks),rks=0,pu(rk),pu(lk);
}
void mksa(LL pos,LL num)
{
LL c=read(),lk=kth(pos-1ll),rk=kth(pos+num);
splay(lk,0),splay(rk,lk),mark(rks,c),pd(rks),pu(rk),pu(lk);
}
void reverse(LL pos,LL num)
{
LL lk=kth(pos-1ll),rk=kth(pos+num);
splay(lk,0),splay(rk,lk),rever(rks),pd(rks),pu(rk),pu(lk);
}
LL getsum(LL pos,LL num)
{
LL lk=kth(pos-1ll),rk=kth(pos+num);
splay(lk,0),splay(rk,lk);
return sum[rks];
}
int main()
{
char s[20];
memset(inf,63,sizeof(inf));
n=read(),m=read();
rep(i,1,n)tmp[i]=read();tmp[0]=tmp[n+1]=-inf[0];
rt=build(0,n+1);
while(m--)
{
scanf("%s",s);
if(s[0]=='I')x=read()+1,y=read(),ins(x,y);
if(s[0]=='D')x=read()+1,y=read(),del(x,y);
if(s[0]=='M'&&s[2]=='K')x=read()+1,y=read(),mksa(x,y);
if(s[0]=='R')x=read()+1,y=read(),reverse(x,y);
if(s[0]=='G')x=read()+1,y=read(),write(getsum(x,y));
if(s[0]=='M'&&s[2]=='X'){if(siz[rt]>2)write(xm[rt]);else write(0);}
}
return 0;
}

　　
最后祝您身体健康，再见。

手机扫一扫

移动阅读更方便

你可能感兴趣的文章