超绝最可爱线段树9pts求条。
查看原帖
超绝最可爱线段树9pts求条。
739258
HanazomeMana楼主2023/9/30 12:33
#include<bits/stdc++.h>
#define p2 p<<1
#define p3 p<<1|1
using namespace std;
typedef long long lint;
lint n,m,a[114514],o,l,r,k,d;
struct Seg{
	lint sum,lz;
}t[415411];
void build(int l,int r,int p){
	int mid=(l+r)/2;
	if(l==r)return t[p].sum=a[l],void();
	build(l,mid,p2),build(mid+1,r,p3),t[p].sum=t[p2].sum+t[p3].sum;
}void pushdown(int p,int l,int r){
	int mid=(l+r)/2;
	t[p2].lz+=t[p].lz,t[p3].lz+=t[p].lz,t[p2].sum+=t[p].lz*(mid-l+1),t[p3].sum+=t[p].lz*(r-mid),t[p].lz=0;
}void update(int l,int r,int x,int y,int p,lint v){
	if(x<=l&&y>=r)return t[p].lz+=v,t[p].sum+=(r-l+1)*v,void();
	pushdown(l,r,p);int mid=(l+r)/2;
	if(x<=mid)update(l,mid,x,y,p2,v);
	if(y>mid)update(mid+1,r,x,y,p3,v);
	t[p].sum=t[p2].sum+t[p3].sum;
}lint query(int l,int r,int x,int y,int p){
	if(x<=l&&y>=r)return t[p].sum;
	pushdown(l,r,p);int mid=(l+r)/2,res=0;
	if(x<=mid)res+=query(l,mid,x,y,p2);
	if(y>mid)res+=query(mid+1,r,x,y,p3);
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=n;i;--i)a[i]-=a[i-1];
	build(1,n,1);
	while(m--){
		cin>>o;
		if(o==1){
			cin>>l>>r>>k>>d,update(1,n,l,l,1,k);
			if(l<r)update(1,n,l+1,r,1,d);
			if(r<n)update(1,n,r+1,r+1,1,-(k+d*(r-l)));
		}else cin>>k,cout<<query(1,n,1,k,1)<<'\n';
	}
	return 0;
}
2023/9/30 12:33
加载中...