初学线段树 10分求助
查看原帖
初学线段树 10分求助
238768
Forest_楼主2021/4/4 16:12

代码参照OI Wiki线段树学习笔记内的示范代码编写

只过了第3个点,求助

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
struct node{
	ll sum,laz;
}t[maxn>>2];
int n,q;
ll a[maxn];
void build(int l,int r,int i)
{
	if(l==r)
	{
		t[i].sum=a[l];
		return ;
	} 
	int mid=(l+r)>>1; 
	build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);
	t[i].sum=t[i<<1].sum+t[(i<<1)|1].sum;
} 
int le,ri;
int getsum(int l,int r,int i)
{
	if(le<=l&&r<=ri) return t[i].sum;
	int mid=(l+r)>>1;
	ll ret=0;
	if(t[i].laz)
	{
		t[i<<1].sum+=t[i].laz*(mid-l+1);
		t[(i<<1)|1].sum+=t[i].laz*(r-mid);
		t[i<<1].laz+=t[i].laz;
		t[(i<<1)|1].laz+=t[i].laz;
	}
	t[i].laz=0;
	if(le<=mid) ret+=getsum(l,mid,i<<1);
	if(mid+1<=ri) ret+=getsum(mid+1,r,(i<<1)|1);
	return ret;
}
ll c;//le,ri 
void update(int l,int r,int i)
{
	if(le<=l&&r<=ri)
	{
		t[i].sum+=c*(r-l+1);
		t[i].laz+=c;
		return ; 
	} 
	int mid=(l+r)>>1;
	if(t[i].laz)
	{
		t[i<<1].sum+=t[i].laz*(mid-l+1);
		t[(i<<1)|1].sum+=t[i].laz*(r-mid);
		t[i<<1].laz=t[(i<<1)|1].laz=t[i].laz;
	}
	t[i].laz=0;
	if(le<mid) update(l,mid,i<<1);
	if(mid+1<=ri) update(mid+1,r,(i<<1)|1);
	t[i].sum=t[i<<1].sum+t[(i<<1)|1].sum;
	return ;
} 
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,n,1);
	int x;
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&x);
		if(x==1)
		{
			scanf("%d%d%lld",&le,&ri,&c);
			update(1,n,1);
		}
		if(x==2)
		{
			scanf("%d%d",&le,&ri);
			printf("%d\n",getsum(1,n,1));
		}
		
	}
	
	return 0;
} 
2021/4/4 16:12
加载中...