求助
  • 板块灌水区
  • 楼主yhy2024
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/27 14:53
  • 上次更新2024/7/27 15:56:19
查看原帖
求助
1262406
yhy2024楼主2024/7/27 14:53
#include<bits/stdc++.h>
#define N 100005 
using namespace std;
int sum[N*4],sumadd[N*4],n,m,a[N*4],x1,y2,k2,b[N*4],k,o,d;//sumadd是懒标记,o是首项,k是公差
void build(int k,int l,int r)
{
	if(l==r)
	{
		sum[k]=b[l];
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	sum[k]=sum[k*2]+sum[k*2+1];
}
void add(int k,int l,int r,int x)
{
	sumadd[k]+=x;
	sum[k]+=(r-l+1)*x;
	return;
} 
void pushdown(int k,int l,int r)
{
	if(sumadd[k]==0)
	{
		return;
	}
	int mid=(l+r)/2;
	add(k*2,l,mid,sumadd[k]);
	add(k*2+1,mid+1,r,sumadd[k]);
	sum[k]=sum[k*2]+sum[k*2+1];
	sumadd[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v) 
{
//	cout<<l<<" "<<r<<endl;
	if(r<x||l>y)return;
	if(l>=x&&r<=y) 
	{
		add(k,l,r,v); 
		return;
	}
	int mid=(l+r)/2;
	pushdown(k,l,r);
	modify(k*2,l,mid,x,y,v);
	modify(k*2+1,mid+1,r,x,y,v);
	sum[k]=sum[k*2+1]+sum[k*2];
}
int query(int k,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		return sum[k];
	}
	int mid=(l+r)/2,res=0;
	pushdown(k,l,r);
	if(x<=mid)
	{
		res+=query(k*2,l,mid,x,y);	
	} 
	if(mid<y)
	{
		res+=query(k*2+1,mid+1,r,x,y);
	}
	return res;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i]-a[i-1];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		cin>>k;
		if(k==2)
		{
			cin>>x1;
			cout<<query(1,1,n,1,x1)<<endl; 	
		} 
		else
		{
			cin>>x1>>y2>>o>>d;
			if(x1<y2) modify(1,1,n,x1+1,y2,d);
			modify(1,1,n,x1,x1,o);
			if(y2<n) modify(1,1,n,y2+1,y2+1,(k+(y2-x1)*d));
		}
	}
	return 0;
} 
2024/7/27 14:53
加载中...