1 条题解

  • 0
    @ 2025-8-24 21:40:42

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar 破忆
    一个loser而已

    搬运于2025-08-24 21:40:42，当前版本为作者最后更新于2020-10-26 13:26:38，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    【题意】

    维护一个序列

    支持插入、删除、翻转、覆盖、求和、求最大子段和操作

    【分析】

    经典数据结构题

    没什么思维难度，直接上fhq−treapfhq-treap吧

    明确需要维护的信息

    翻转和覆盖，需要打两个懒标记

    求和需要区间和

    求最大子段和需要区间最大前缀、最大后缀与最大子段和

    还有随机键值、区间大小、左右子树

    struct fhq_treap{
	int rand,siz,rev,cov,son[2],val;
	LL max,s,l,r;
}t[maxt];

    上传信息、下发标记

    线段树和平衡树的基本操作，比较套路

    IN void pushup(RE int k){
	t[k].siz=t[ls].siz+t[rs].siz+1;
	t[k].s=t[ls].s+t[rs].s+t[k].val;
	t[k].l=max(t[ls].l,max(0ll,t[ls].s+t[k].val+t[rs].l));
	t[k].r=max(t[rs].r,max(0ll,t[rs].s+t[k].val+t[ls].r));
	t[k].max=max((LL)t[k].val,t[ls].r+t[k].val+t[rs].l);
	if(ls) t[k].max=max(t[k].max,t[ls].max);
	if(rs) t[k].max=max(t[k].max,t[rs].max);
}

    IN void pushdown(RE int k){
	if(t[k].cov!=INF){
		LL c=t[k].cov;
		if(ls) cov(ls,c);
		if(rs) cov(rs,c);
		t[k].cov=INF;
	}
	if(t[k].rev){
		if(ls) rev(ls);
		if(rs) rev(rs);
		t[k].rev=0;
	}
}

    fhq-treap合并、分裂板子

    int merge(RE int x,RE int y){
	if(!x||!y) return x+y;
	if(t[x].rand<t[y].rand){
		pushdown(x);
		t[x].son[1]=merge(t[x].son[1],y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		t[y].son[0]=merge(x,t[y].son[0]);
		pushup(y);
		return y;
	}
}

    void splits(RE int now,RE int k,RE int &x,RE int &y){
	if(!now){
		x=y=0;
		return;
	}
	pushdown(now);
	if(k<=t[t[now].son[0]].siz){
		y=now;
		splits(t[y].son[0],k,x,t[y].son[0]);
		pushup(y);
	}
	else{
		x=now;
		splits(t[x].son[1],k-t[t[x].son[0]].siz-1,t[x].son[1],y);
		pushup(x);
	}
	pushup(now);
}

    插入与删除

    插入仿照线段树建树方式，而不是逐个插入，可以更平衡

    删点时把没用的点存入栈，以便下次使用

    IN int build(RE int k){
	RE int now=top?stk[top--]:++cnt;
	t[now].rand=rand();
	t[now].cov=INF;
	t[now].rev=0;
	t[now].son[0]=t[now].son[1]=0;
	t[now].max=t[now].s=t[now].val=k;
	t[now].l=t[now].r=max(k,0);
	t[now].siz=1;
	return now;
}
int build(RE int l,RE int r){
	if(l==r) return build(read());
	int x=build(l,mid),y=build(mid+1,r);
	return merge(x,y);
}

    void del(RE int k){
	if(ls) del(ls);
	if(rs) del(rs);
	stk[++top]=k;
}
IN void del(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	del(y);
	rt=merge(x,z);
}

    覆盖与翻转

    分离出待操作区间，然后打上标记，顺便更新信息

    IN void cov(RE int k,RE int c){
	t[k].cov=t[k].val=c;
	t[k].s=(LL)t[k].siz*c;
	t[k].l=t[k].r=max(0ll,t[k].s);
	t[k].max=max((LL)c,t[k].s);
}

IN void cover(RE int l,RE int r,RE int c){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	cov(y,c);
	rt=merge(merge(x,y),z);
}

    IN void rev(RE int k){
	if(!k) return;
	swap(t[k].l,t[k].r);
	swap(t[k].son[0],t[k].son[1]);
	t[k].rev^=1;
}
IN void reverse(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	rev(y);
	rt=merge(merge(x,y),z);
}

    询问

    分离出区间输出即可

    IN LL query(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	RE LL ret=t[y].s;
	rt=merge(merge(x,y),z);
	return ret;
}

    IN LL maxs(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	LL ret=t[y].max;
	rt=merge(merge(x,y),z);
	return ret;
}

    算法

    fhq-treap

    提醒

    细节多，代码长

    以下几个地方值得注意

    翻转时要交换最大前缀和最大后缀

    下传标记时，先覆盖再翻转

    建树时，先提取出子树再合并，不能写成这样，否则会有意想不到的错误

    merge(build(l,mid),build(mid+1,r))

    若没有覆盖标记时，懒标记应该设置成一个不可能出现的值，设成-1,0之类的就完了

    记得开longlong

    代码

    #include<bits/stdc++.h>
#define LL long long
#define ls t[k].son[0]
#define rs t[k].son[1]
#define mid (l+r>>1)
#define IN inline
#define RE register
using namespace std;
const int maxt=5e5+5,INF=1<<30;
int n,m;
int top,stk[maxt];
int cnt,rt;
char z[15];
struct fhq_treap{
	int rand,siz,rev,cov,son[2],val;
	LL max,s,l,r;
}t[maxt];
IN int read(){
	RE int ret=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
IN void rev(RE int k){
	if(!k) return;
	swap(t[k].l,t[k].r);
	swap(t[k].son[0],t[k].son[1]);
	t[k].rev^=1;
}
IN void cov(RE int k,RE int c){
	t[k].cov=t[k].val=c;
	t[k].s=(LL)t[k].siz*c;
	t[k].l=t[k].r=max(0ll,t[k].s);
	t[k].max=max((LL)c,t[k].s);
}
IN void pushup(RE int k){
	t[k].siz=t[ls].siz+t[rs].siz+1;
	t[k].s=t[ls].s+t[rs].s+t[k].val;
	t[k].l=max(t[ls].l,max(0ll,t[ls].s+t[k].val+t[rs].l));
	t[k].r=max(t[rs].r,max(0ll,t[rs].s+t[k].val+t[ls].r));
	t[k].max=max((LL)t[k].val,t[ls].r+t[k].val+t[rs].l);
	if(ls) t[k].max=max(t[k].max,t[ls].max);
	if(rs) t[k].max=max(t[k].max,t[rs].max);
}
IN void pushdown(RE int k){
	if(t[k].cov!=INF){
		LL c=t[k].cov;
		if(ls) cov(ls,c);
		if(rs) cov(rs,c);
		t[k].cov=INF;
	}
	if(t[k].rev){
		if(ls) rev(ls);
		if(rs) rev(rs);
		t[k].rev=0;
	}
}
void splits(RE int now,RE int k,RE int &x,RE int &y){
	if(!now){
		x=y=0;
		return;
	}
	pushdown(now);
	if(k<=t[t[now].son[0]].siz){
		y=now;
		splits(t[y].son[0],k,x,t[y].son[0]);
		pushup(y);
	}
	else{
		x=now;
		splits(t[x].son[1],k-t[t[x].son[0]].siz-1,t[x].son[1],y);
		pushup(x);
	}
	pushup(now);
}
int merge(RE int x,RE int y){
	if(!x||!y) return x+y;
	if(t[x].rand<t[y].rand){
		pushdown(x);
		t[x].son[1]=merge(t[x].son[1],y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		t[y].son[0]=merge(x,t[y].son[0]);
		pushup(y);
		return y;
	}
}
IN int build(RE int k){
	RE int now=top?stk[top--]:++cnt;
	t[now].rand=rand();
	t[now].cov=INF;
	t[now].rev=0;
	t[now].son[0]=t[now].son[1]=0;
	t[now].max=t[now].s=t[now].val=k;
	t[now].l=t[now].r=max(k,0);
	t[now].siz=1;
	return now;
}
void del(RE int k){
	if(ls) del(ls);
	if(rs) del(rs);
	stk[++top]=k;
}
int build(RE int l,RE int r){
	if(l==r) return build(read());
	int x=build(l,mid),y=build(mid+1,r);
	return merge(x,y);
}
IN void del(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	del(y);
	rt=merge(x,z);
}
IN void cover(RE int l,RE int r,RE int c){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	cov(y,c);
	rt=merge(merge(x,y),z);
}
IN void reverse(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	rev(y);
	rt=merge(merge(x,y),z);
}
IN LL query(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	RE LL ret=t[y].s;
	rt=merge(merge(x,y),z);
	return ret;
}
IN LL maxs(RE int l,RE int r){
	RE int x,y,z;
	splits(rt,r,x,z);
	splits(x,l-1,x,y);
	LL ret=t[y].max;
	rt=merge(merge(x,y),z);
	return ret;
}
int main(){
	freopen("P2710.in","r",stdin);
	freopen("P2710.out","w",stdout);
	n=read(),m=read();
	rt=build(1,n);
	for(RE int i=1;i<=m;i++){
		scanf("%s",z);
		if(z[0]=='I'){
			RE int pos=read(),tot=read();
			RE int x,y;
			splits(rt,pos,x,y);
			rt=merge(merge(x,build(pos,pos+tot-1)),y);
		}else
		if(z[0]=='D'){
			RE int pos=read(),tot=read();
			del(pos,pos+tot-1);
		}else
		if(z[0]=='R'){
			RE int pos=read(),tot=read();
			reverse(pos,pos+tot-1);
		}else
		if(z[2]=='K'){
			RE int pos=read(),tot=read(),c=read();
			cover(pos,pos+tot-1,c);
		}else
		if(z[1]=='A'){
			RE int pos=read(),tot=read();
			printf("%lld\n",maxs(pos,pos+tot-1));
		}else
		if(strlen(z)>4){
			RE int pos=read(),tot=read();
			printf("%lld\n",query(pos,pos+tot-1));
		}
		else{
 			RE int pos=read();
			printf("%lld\n",query(pos,pos));
		}
	}
	return 0;
}

    最后

    保持一个平和的心态

    • 1

    数列

    信息

    ID
    1747
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 19ms