线段树求助(re50分)
  • 板块P2781 传教
  • 楼主hereisyy
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/12/4 20:17
  • 上次更新2023/10/27 00:27:58
查看原帖
线段树求助(re50分)
747551
hereisyy楼主2022/12/4 20:17

我是小弱鸡,re50分求助

#include<iostream>
#define ls k<<1
#define rs k<<1|1
#define int long long 
using namespace std;
const int N=1e8+10;
struct{
	int l,r;
	int sum,lazy;
}f[N<<2];
void pushup(int k){
	f[k].sum=f[ls].sum+f[rs].sum;
}
void build(int k,int l,int r){
	f[k].l=l;
	f[k].r=r;
	if(l==r)
		return;
	int m=l+r>>1;
	build(ls,l,m);
	build(rs,m+1,r);
	pushup(k); 
}
void pushdown(int k){
	if(f[k].lazy){
		f[ls].sum+=f[k].lazy*(f[ls].r-f[ls].l+1);
		f[rs].sum+=f[k].lazy*(f[rs].r-f[rs].l+1);
		f[ls].lazy+=f[k].lazy;
		f[rs].lazy+=f[k].lazy;
		f[k].lazy=0;
	}
}
void add(int k,int l,int r,int d){
	if(l<=f[k].l&&f[k].r<=r){
		f[k].sum+=d*(f[k].r-f[k].l+1);
		f[k].lazy+=d;
		return;
	}
	pushdown(k);
	int m=f[k].l+f[k].r>>1;
	if(l<=m)
		add(ls,l,r,d);
	if(m<r)
		add(rs,l,r,d);
	pushup(k);
}
int query(int k,int l,int r){
	int res=0;
	if(l<=f[k].l&&f[k].r<=r)
		return f[k].sum;
	pushdown(k);
	int m=f[k].l+f[k].r>>1;
	if(l<=m)
		res+=query(ls,l,r);
	if(m<r)	
		res+=query(rs,l,r);
	return res;
}
signed main(){
	int n,m,op,x,y,z;
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>op>>x>>y;
		if(op==1){
			cin>>z;
			add(1,x,y,z);
		}
		else{
			cout<<query(1,x,y)<<"\n";
		}
	}
	return 0;
}
2022/12/4 20:17
加载中...