社区讨论

线段树过不了样例求调

P3372【模板】线段树 1参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo7lb34x
此快照首次捕获于
2023/10/27 03:41
2 年前
此快照最后确认于
2023/10/27 03:41
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],op,x,y,k,sum[1000005],la[400005];
void build(long long pos,long long l,long long r)
{
	if(l==r)
	{
        
		sum[pos]=a[l];
        //cout<<pos<<' '<<l<<' '<<r<<' '<<sum[pos]<<endl;
		return;
	}
	long long mid=(l+r)/2;
	build(pos*2,l,mid);
	build(pos*2+1,mid+1,r); 
    
	sum[pos]=sum[pos*2]+sum[pos*2+1];
   // cout<<pos<<' '<<l<<' '<<r<<' '<<sum[pos]<<endl;
}
void down(long long pos,long long l,long long r)
{
	la[pos*2]+=la[pos];
	la[pos*2+1]+=la[pos];
	la[pos]=0;
	long long mid=(l+r)/2;
    sum[pos*2]+=la[pos*2]*(mid-l+1);
    sum[pos*2+1]+=la[pos*2+1]*(r-mid);
    sum[pos]=sum[pos*2]+sum[pos*2+1];
}
void add(long long pos,long long l,long long r,long long el,long long er,long long k)
{
	if(r<el||er<l)return;
	if(el<=l&&r<=er)
	{
		sum[pos]+=k*(r-l+1);
		la[pos]+=k;
		return;
	}
    down(pos,l,r);
	long long mid=(l+r)/2;
	add(pos*2,l,mid,el,er,k);
	add(pos*2+1,mid+1,r,el,er,k); 
	sum[pos]=sum[pos*2]+sum[pos*2+1];	
}
long long query(long long pos,long long l,long long r,long long el,long long er)
{
    
	if(r<el||er<l)return 0;
	if(el<=l&&r<=er)
	{
     //   cout<<pos<<' '<<l<<' '<<r<<' '<<el<<' '<<er<<' '<<sum[pos]<<endl; 
		return sum[pos];
	}
    
	down(pos,l,r);
	long long mid=(l+r)/2;
   //cout<<pos<<l<<' '<<r<<' '<<el<<' '<<er<<' '<<query(pos*2,l,mid,el,er)+query(pos*2+1,mid+1,r,el,er)<<endl; 
	return query(pos*2,l,mid,el,er)+query(pos*2+1,mid+1,r,el,er); 
		
}
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++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			add(1,1,n,x,y,k); 
		}
		if(op==2) 
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<endl;
		}
	}
}

回复

2 条回复,欢迎继续交流。

正在加载回复...