P3368 线段树求调
  • 板块题目总版
  • 楼主MunYixty
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/2/25 21:07
  • 上次更新2023/10/23 23:46:32
查看原帖
P3368 线段树求调
868365
MunYixty楼主2023/2/25 21:07
#include<bits/stdc++.h>
using namespace std; 
int n,m;
int a[500005];
struct AA
{
	int l,r;
	long long lazy,s;
}t[500005*4];
void build(int i,int l,int r)
{
	t[i].l=l,t[i].r=r;
	if(l==r)
	{
		t[i].s=a[l];
		return;
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2,mid+1,r);
	t[i].s=t[i*2].s+t[i*2+1].s;
	
}
void lazytap(int i)
{
	if(t[i].lazy)
	{
		t[i*2].s=t[i].lazy*(t[i*2].r-t[i*2].l+1);
		t[i*2].lazy+=t[i].lazy;
		t[i*2+1].s=t[i].lazy*(t[i*2+1].r-t[i*2+1].l+1);
		t[i*2+1].lazy+=t[i].lazy;
		t[i].lazy=0;
	}
}
void change(int i,int l,int r,long long k)
{
	if(t[i].l>=l&&t[i].r<=r)
	{
		t[i].s+=k*(t[i].r-t[i].l+1);
		t[i].lazy+=k;
		return;
	}
	lazytap(i);
	int mid=t[i].l+t[i].r>>1;
	if(l<=mid)change(i*2,l,r,k);
	if(r>mid)change(i*2+1,l,r,k);
	t[i].s=t[i*2].s+t[i*2+1].s;
}
long long que(int i,int x)
{
	if(t[i].l==x&&t[i].r==x)
	{
		return t[i].s;
	}
	lazytap(i);
	long long ans=0;
	int mid=t[i].l+t[i].r>>1;
	if(x<=mid)
	{
		ans+=que(i*2,x);
	}
	if(x>mid)
	{
		ans+=que(i*2+1,x);
		
	}
	return ans;
}
int main()
{ 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int x,y;
			long long z;
			scanf("%d%d",&x,&y);
			cin>>z;	
			change(1,x,y,z);
		}
		if(op==2)
		{
			int x;
			scanf("%d",&x);
			cout<<que(1,x)<<endl;
		}	
	}
	return 0; 
}
2023/2/25 21:07
加载中...