我真的连板子都敲不好
查看原帖
我真的连板子都敲不好
164840
zhaowangji楼主2020/7/24 18:40

真的不知道错在哪里。。。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100007];
struct SegmentTree{
	int l,r;
	int sum;
	int f;
}t[400007];
void pushup(int id){
	t[id].sum=t[id*2].sum+t[id*2+1].sum;
	return;
}
void build(int id,int l,int r){
	t[id].l=l;t[id].r=r;
	if(l==r){t[id].sum=a[id];return;}
	int mid=(l+r)>>1;
	build(id*2,l,mid);build(id*2+1,mid+1,r);
	return;
}
void pushdown(int id){
	if(t[id].f){
		t[id*2].sum+=t[id].f*(t[id*2].r-t[id*2].l+1);
		t[id*2+1].sum+=t[id].f*(t[id*2+1].r-t[id*2+1].l+1);
		t[id*2].f+=t[id].f;
		t[id*2+1].f+=t[id].f;
		t[id].f=0;
	}
	return;
}
void update(int id,int l,int r,int k){
	if(l<=t[id].l&&t[id].r<=r){
		t[id].sum+=k*(t[id].r-t[id].l+1);
		t[id].f+=k;
		return;
	}
	pushdown(id);
	int mid=(t[id].l+t[id].r)>>1;
	if(l<=mid)update(id*2,l,r,k);
	if(r>mid)update(id*2+1,l,r,k);
	pushup(id);
	return;
}
int query(int id,int l,int r){
	if(l<=t[id].l&&t[id].r<=r)return t[id].sum;
	pushdown(id);
	int mid=(t[id].l+t[id].r)>>1;
	if(r<=mid)return query(id*2,l,r);
	else if(l>mid)return query(id*2+1,l,r);
	else return query(id*2,l,r)+query(id*2+1,l,r);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;++i){
		char jud;cin>>jud;
		if(jud=='1'){
			int x,y,k;cin>>x>>y>>k;
			update(1,x,y,k);
		}
		else{
			int x,y;cin>>x>>y;
			cout<<query(1,x,y)<<endl;
		}
	}
	return 0;
}

感谢

2020/7/24 18:40
加载中...