进食后人
  • 板块P2781 传教
  • 楼主Mii2308
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/22 14:43
  • 上次更新2025/7/22 18:43:02
查看原帖
进食后人
1451441
Mii2308楼主2025/7/22 14:43

如果你选择动态开点线段树解题,并且找不到RE/TLERE/TLE onon 2,102,10的原因,如:

struct Tree{
	ll l,r,ls,rs;//节点边界,子节点编号 
	ll v,lazy;
	ll len(){return r-l+1;}
}tr[3003];
int root,tot;
inline int build(ll l,ll r){
	tot++;
	tr[tot].l=l;tr[tot].r=r;
	tr[tot].v=0;tr[tot].lazy=0;
	tr[tot].ls=0;tr[tot].rs=0;
	return tot;
}
inline void pushdown(ll p){
	if(tr[p].l==tr[p].r){
		tr[p].lazy=0;return;
	} 
	if(tr[p].lazy){
		ll l=tr[p].l,r=tr[p].r;
		ll mid=(l+r)>>1;
		if(tr[p].ls==0){tr[p].ls=build(l,mid);}
		if(tr[p].rs==0){tr[p].rs=build(mid+1,r);}
		int pl=tr[p].ls,pr=tr[p].rs;
		tr[pl].v+=tr[p].lazy*tr[pl].len();
		tr[pl].lazy+=tr[p].lazy;
		tr[pr].v+=tr[p].lazy*tr[pr].len();
		tr[pr].lazy+=tr[p].lazy;
		tr[p].lazy=0;
	}//leaps? 
}
inline void pushup(int p){
	tr[p].v=0;
	if(tr[p].ls) tr[p].v+=tr[tr[p].ls].v;
	if(tr[p].rs) tr[p].v+=tr[tr[p].rs].v;
}
inline void update(int p,ll vl,ll vr,ll v){
	if(vl<=tr[p].l&&vr>=tr[p].r){
		tr[p].v+=v*tr[p].len();
		tr[p].lazy+=v;return;
	}pushdown(p);
	ll l=tr[p].l,r=tr[p].r;ll mid=(l+r)>>1;
	if(vl<=mid){ //vl
		if(tr[p].ls==0) tr[p].ls=build(l,mid);
		update(tr[p].ls,vl,vr,v);
	}
	if(vr>mid){ //vr
		if(tr[p].rs==0) tr[p].rs=build(mid+1,r);
		update(tr[p].rs,vl,vr,v);
	}
	pushup(p);
}
inline ll query(ll p,ll vl,ll vr){
	if(p==0||vr<tr[p].l||vl>tr[p].r) return 0;
	if(vl<=tr[p].l&&vr>=tr[p].r)return tr[p].v;
	pushdown(p);
	ll v=0,l=tr[p].l,r=tr[p].r;ll mid=(l+r)>>1;
	if(vl<=mid) v+=query(tr[p].ls,vl,vr);
	if(vr>mid) v+=query(tr[p].rs,vl,vr);
	return v;
}

请检查你的数组是否开小了,你的变量名用的对不对。

2025/7/22 14:43
加载中...