未知的WA! dalao求条,悬1
查看原帖
未知的WA! dalao求条,悬1
808773
forever516楼主2024/9/3 20:14

线段树太难调了,求大佬指出错误。 (蒟蒻未过样例)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,m,t[N<<2],ta[N<<2],a[N];
ll ls(ll l){return (l<<1);}
ll rs(ll r){return (r<<1)|1;}
void push(ll p){t[p]=t[ls(p)]+t[rs(p)];}
void bu(ll p,ll pl,ll pr){
	ta[p]=0;
	if(pl==pr){
		t[p]=a[pl];
		return ;
	}
	ll mid=(pl+pr)>>1;
	bu(ls(p),pl,mid);
	bu(ls(p),mid+1,pr);
	push(p);
}
void at(ll p,ll pl,ll pr,ll d){
	ta[p]+=d;
	t[p]+=d*(pr-pl+1);
}
void pd(ll p,ll pl,ll pr){
	if(ta[p]){
		ll mid=(pl+pr)>>1;
		at(ls(p),pl,mid,ta[p]);
		at(rs(p),mid+1,pr,ta[p]);
		ta[p]=0;
	}
}
void ud(ll L,ll R,ll p,ll pl,ll pr,ll d){
	if(L<=pl&&pr<=R){
		at(p,pl,pr,d);
		return ;
	}
	pd(p,pl,pr);
	ll mid=(pl+pr)>>1;
	if(L<=mid)ud(L,R,ls(p),pl,mid,d);
	if(R>mid)ud(L,R,rs(p),mid+1,pr,d);
	push(p);
}
ll qu(ll L,ll R ,ll p,ll pl,ll pr){
	if(pl>=L&&pr<=R)return t[p];
	pd(p,pl,pr);
	ll re=0,mid=(pl+pr)>>1;
	if(L<=mid)re+=qu(L,R,ls(p),pl,mid);
	if(R>mid)re+=qu(L,R,rs(p),mid+1,pr);
	return re;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++)cin>>a[i];
	bu(1,1,n);
	while(m--){
		ll q,L,R,d;
		cin>>q;
		if(q==1){
			cin>>L>>R>>d;
			ud(L,R,1,1,n,d);
		}else{
			cin>>L>>R;
			cout<<qu(L,R,1,1,n)<<"\n";
		}
	}
	
	return 0;
}
2024/9/3 20:14
加载中...