萌新刚学OI,改数小时未果
  • 板块学术版
  • 楼主_yjh
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/5 22:05
  • 上次更新2023/11/6 21:11:30
查看原帖
萌新刚学OI,改数小时未果
222104
_yjh楼主2020/8/5 22:05

求各位大佬帮忙查一下错误,刚学数据结构,自己也找不出错误QAQ

题目链接:点我

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,m,sum,a[100050],Node[400050],lazy[400050];
void push_up(ll t) {
	Node[t]=Node[t<<1]+Node[t<<1|1];
}
void push_down(ll t,ll m) {
	if(lazy[t]!=0) {
		lazy[t<<1]+=lazy[t];
		lazy[t<<1|1]+=lazy[t];
		Node[t<<1]+=lazy[t]*(m-(m>>1));
		Node[t<<1|1]+=lazy[t]*(m>>1);
		lazy[t]=0;
	}
} 
void Build(ll t,ll l,ll r) {
	if(l==r) {
		Node[t]=a[l];
		return ;
	}
	ll mid=(l+r)/2;
	Build(2*t,l,mid);
	Build(2*t+1,mid+1,r);
	push_up(t); 
}
void Add(ll t,ll l,ll r,ll l1,ll r1,ll x) {
	if(l>=l1&&r<=r1) {
		lazy[t]+=x;
		Node[t]+=(r-l+1)*x;
		return ;
	}
	push_down(t,r-l+1);
	ll mid=(l+r)/2;
	if(l1<=mid) {
		Add(t*2,l,mid,l1,r1,x);
	}
	if(r1>=mid+1) {
		Add(t*2+1,mid+1,r,l1,r1,x);
	}
	push_up(t); 
}
void Find(long long t,long long l,long long r,ll l1,ll r1) {
	if(l>=l1&&r<=r1) {
		sum+=Node[t];
		return ;
	}
	push_down(t,r-l+1);
	long long mid=(l+r)/2;
	if(l1<=mid) Find(t*2,l,mid,l1,r1);
	if(r1>=mid+1) Find(t*2+1,mid+1,r,l1,r1);
}
int main() {
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
	}
	while(m--) {
		ll team;
		scanf("%lld",&team);
		if(team==1) {
			ll x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			Add(1,1,n,x,y,k);
		}
		else {
			sum=0;
			ll x,y;
			scanf("%lld%lld",&x,&y);
			Find(1,1,n,x,y);
			printf("%lld\n",sum);
		}
	}
	return 0;
}
2020/8/5 22:05
加载中...