线段树模板求调
查看原帖
线段树模板求调
422996
HeCao2008楼主2022/8/11 13:01

rt,为什么RE了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000010;
ll n,m;
ll a[maxn],ans[maxn<<2],lazy_tag[maxn<<2];
inline ll left_kid(ll x){
	return x<<1;
} 
inline ll right_kid(ll x){
	return x<<1|1; 
} 
inline void keep_push_up(ll id){
	ans[id]=ans[left_kid(id)]+ans[right_kid(id)];
} 
void build_tree(ll id,ll l,ll r){
	lazy_tag[id]=0; 
	if(l==r){
		ans[id]=a[l];
		return;
	} 
	ll mid=l+(r-l)/2;
	build_tree(left_kid(id),l,mid);
	build_tree(right_kid(id),mid+1,r);
	keep_push_up(id);
} 
inline void use_lazy_tag(ll id,ll l,ll r,ll k){
	
	lazy_tag[id]+=k; 
	ans[id]+=k*(r-l+1); 
} 
inline void keep_push_down(ll id,ll l,ll r){ 
	ll mid=l+(r-l)/2;
	use_lazy_tag(left_kid(id),l,mid,lazy_tag[id]);
	use_lazy_tag(right_kid(id),mid+1,r,lazy_tag[id]);
	
} 
inline void return_num_up(ll now_l,ll now_r,ll l,ll r,ll id,ll k){
	
	if(now_l<=l&&r<=now_r){  
		ans[id]+=k*(r-l)+1;
		lazy_tag[id]+=k;
		return;
	}
	keep_push_down(id,l,r); 
	ll mid=l+(r-l)/2;
	if(now_l<=mid)return_num_up(now_l,now_r,l,mid,left_kid(id),k);
	if(now_r>mid)return_num_up(now_l,now_r,mid+1,r,right_kid(id),k);
	keep_push_up(id);
} 
ll ask(ll x,ll y,ll l,ll r,ll id){
    ll aans=0;
	if(x<=l&&r<=y)return ans[id];
	ll mid=l+(r-l)/2;
	keep_push_down(id,l,r);
	if(x<=mid)aans+=ask(x,y,l,mid,left_kid(id));
	if(y>mid)aans+=ask(x,y,mid+1,r,right_kid(id));
	return aans; 
}
int main(){
	build_tree(1,1,n);
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); 
	for(ll i=1;i<=m;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			ll xx,yy,kk;
			scanf("%lld%lld%lld",&xx,&yy,&kk);
			return_num_up(xx,yy,1,n,1,kk);
		}
		if(op==2){
			ll xxx,yyy;
			scanf("%lld%lld",&xxx,&yyy);
			printf("%lld\n",ask(xxx,yyy,1,n,1));
		}
	} 
	return 0;
}
2022/8/11 13:01
加载中...