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

传送门->

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

其实这题应该口胡很容易。操作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<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#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;

}

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

巴特西

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

最新文章

热门文章