P2042 [NOI2005] 维护数列

FHQ Treap 10pts WA

#include<bits/stdc++.h>
#define LL long long
#define N 4000010
using namespace std;
int n,m;

int rt,ls[N],rs[N],pri[N],siz[N];

int top,stk[N];

LL tag[N],sum[N],num[N];

LL lmn[N],rmn[N],mmn[N];

bool mdf[N],rev[N];

mt19937 rng(time(0));

void pushup(int q)
{
	sum[q]=sum[ls[q]]+sum[rs[q]]+num[q];
	siz[q]=siz[ls[q]]+siz[rs[q]]+1;
	
	lmn[q]=max(max(lmn[ls[q]],sum[ls[q]]+num[q]),sum[ls[q]]+num[q]+lmn[rs[q]]);
	rmn[q]=max(max(rmn[rs[q]],sum[rs[q]]+num[q]),sum[rs[q]]+num[q]+rmn[ls[q]]);
	mmn[q]=max(max(num[q],rmn[ls[q]]+num[q]+lmn[rs[q]]),max(rmn[ls[q]]+num[q],num[q]+lmn[rs[q]]));
	return;
}
void modify(int q,LL val)
{
	tag[q]=val;
	mdf[q]=true;
	sum[q]=val*siz[q];
	num[q]=val;
	if(val>0)
	{
		lmn[q]=val*siz[q];
		rmn[q]=val*siz[q];
		mmn[q]=val*siz[q];
	}
	else
	{
		lmn[q]=val;
		rmn[q]=val;
		mmn[q]=val;
	}
	return;
}
void reverse(int q)
{
	rev[q]^=1;
	swap(ls[q],rs[q]);
	swap(lmn[q],rmn[q]);
	return;
}
void pushdown(int q)
{
	if(mdf[q])
	{
		modify(ls[q],tag[q]);
		modify(rs[q],tag[q]);
		mdf[q]=false;
	}
	if(rev[q])
	{
		reverse(ls[q]);
		reverse(rs[q]);
		rev[q]=false;
	}
	return;
}
int merge(int l,int r)
{
	if(l==0||r==0) 
	{
		return l+r;
	}
	if(pri[l]>pri[r]) 
	{
		pushdown(l);
		rs[l]=merge(rs[l],r);
		pushup(l);
		return l;
	}
	else
	{
		pushdown(r);
		ls[r]=merge(l,ls[r]);
		pushup(r);
		return r;
	}
}
void split(int q,int k,int &l,int &r)
{
	if(q==0)
	{
		l=r=0;
		return;
	}
	pushdown(q);
	if(siz[ls[q]]+1<=k)
	{
		l=q;
		split(rs[q],k-siz[ls[q]]-1,rs[q],r);
	}
	else
	{
		r=q;
		split(ls[q],k,l,ls[q]);
	}
	pushup(q);
	return;
}
int newindex()
{
	int tmp=stk[--top];
	if(ls[tmp]) stk[top++]=ls[tmp];
	if(rs[tmp]) stk[top++]=rs[tmp];
	return tmp;
}
int newnode(int val)
{
	int tmp=newindex();
	pri[tmp]=rng();
	ls[tmp]=rs[tmp]=0;
	lmn[tmp]=rmn[tmp]=mmn[tmp]=val;
	sum[tmp]=num[tmp]=val;
	tag[tmp]=0;
	rev[tmp]=mdf[tmp]=false;
	siz[tmp]=1;
	return tmp;
}
void INSERT()
{
	int pos,cnt,x,a,b;
	scanf("%d%d",&pos,&cnt);
	split(rt,pos,a,b);
	for(int i=1;i<=cnt;i++)
	{
		scanf("%d",&x);
		a=merge(a,newnode(x));
	}
	rt=merge(a,b);
	return;
}
void DELETE()
{
	int pos,cnt,a,b,c;
	scanf("%d%d",&pos,&cnt);
	split(rt,pos-1,a,b);
	split(b,cnt,b,c);
	stk[top++]=b;
	rt=merge(a,c);
	return;
}
void MAKE_SAME()
{
	int pos,cnt,x,a,b,c;
	scanf("%d%d%d",&pos,&cnt,&x);
	split(rt,pos-1,a,b);
	split(b,cnt,b,c);
	modify(b,x);
	rt=merge(merge(a,b),c);
	return;
}
void REVERSE()
{
	int pos,cnt,a,b,c;
	scanf("%d%d",&pos,&cnt);
	split(rt,pos-1,a,b);
	split(b,cnt,b,c);
	reverse(b);
	rt=merge(merge(a,b),c);
	return;
}
void GET_SUM()
{
	int pos,cnt,a,b,c;
	scanf("%d%d",&pos,&cnt);
	split(rt,pos-1,a,b);
	split(b,cnt,b,c);
	printf("%lld\n",sum[b]);
	rt=merge(merge(a,b),c);
	return;
}
void MAX_SUM()
{
	printf("%lld\n",max(mmn[rt],max(lmn[rt],rmn[rt])));
	return;
}
signed main()
{
//	freopen("P2042_2.in","r",stdin);
//	freopen("aha.out","w",stdout);

	for(int i=N-1;i>=1;i--)
	{
		stk[top++]=i;
	}
	scanf("%d%d",&n,&m);
	int t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		rt=merge(rt,newnode(t));
	}
	char op[10];
	while(m--)
	{
		scanf("%s",op);
		if(op[0]=='I') 
		{
			INSERT();
		}
		else if(op[0]=='D')
		{
			DELETE();
		}
		else if(op[0]=='M'&&op[2]=='K')
		{
			MAKE_SAME();
		}
		else if(op[0]=='R')
		{
			REVERSE();
		}
		else if(op[0]=='G')
		{
			GET_SUM();
		}
		else
		{
			MAX_SUM();
		}
	}
	return 0;
}