9pt求调 线段树查封
查看原帖
9pt求调 线段树查封
1111313
ZCfree楼主2024/9/19 13:48
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6;
int a[N],tr[N],lazy[N];
int n,m;
int num[N];
inline void push_up(int id)
{
	tr[id]=tr[id*2]+tr[id*2+1];
}
inline void push_down(int id,int l,int r)
{
	if(lazy[id])
	{
		int mid = (l+r)>>1;
		lazy[id*2]+=lazy[id];
		lazy[id*2+1]+=lazy[id];
		tr[id*2]+=lazy[id]*(mid-l+1);
		tr[id*2+1]+=lazy[id]*(r-mid);
		lazy[id]=0;
	}
}
inline void build(int id, int l,int r)
{
	lazy[id]=0;
	if(l==r)
	{
		tr[id]=num[l];
		return;
	}
	int mid = (l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	push_up(id);
}
inline void update(int id,int l,int r,int x,int y,int v)
{
	if(x<=l&&r<=y)
	{
		lazy[id]+=v;
		tr[id]+=v*(r-l+1);
		return;
	}
	int mid=(l+r)>>1;
	push_down(id,l,r);
	if(x<=mid)
	{
		update(id*2,l,mid,x,y,v);
	}
	if(y>mid)
	{
		update(id*2+1,mid+1,r,x,y,v);
	}
	push_up(id);
}

inline int find(int id,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		return tr[id];
	}
	int mid=(l+r)>>1,all=0;
	push_down(id,l,r);
	if(x<=mid)
	{
		all+=find(id*2,l,mid,x,y);
	}
	if(y>mid) 
	{
		all+=find(id*2+1,mid+1,r,x,y);
	}
	return all;
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
	}
	for(int i=n-1;i>0;i--)
	{
		num[i+1]=num[i+1]-num[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		if(x==1)
		{
			int l,r,k,d;
			cin>>l>>r>>k>>d;
			update(1,1,n,l,l,k);
			if(l+1<=r)
			{
				update(1,1,n,l+1,r,d);
			}
			
			if(r<n)
			{
				update(1,1,n,r+1,r+1,-(k+d*(r-l)));
			}
			
		}
		else
		{
			int t;
			cin>>t;
			cout<<find(1,1,n,1,t);
		}
	}
}

2024/9/19 13:48
加载中...