求助,80pts,MLE on #2,#10
  • 板块P2781 传教
  • 楼主Mii2308
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/22 13:35
  • 上次更新2025/7/22 14:43:30
查看原帖
求助,80pts,MLE on #2,#10
1451441
Mii2308楼主2025/7/22 13:35
#include<iostream>
#define ll long long
using namespace std;
int n,m;
//动态开点线段树,下标为操作顺序(乱的),节点要存 
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){
	if(tot>=3000) return 0;
	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].ls==0)return;}
		if(tr[p].rs==0){tr[p].rs=build(mid+1,r);if(tr[p].rs==0)return;}
		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;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	cin>>n>>m;
	tot=0;root=build(1,n);
	for(int i=1;i<=m;i++){
		int t,l,r,w;
		cin>>t>>l>>r;
		if(t==1){
			cin>>w;
			update(root,l,r,w);
		}
		else cout<<query(root,l,r)<<"\n";
	}
	return 0;
}
2025/7/22 13:35
加载中...