9pts纯线段树无差分求调(byd居然没有题解像我一样按照洛谷教材写)
查看原帖
9pts纯线段树无差分求调(byd居然没有题解像我一样按照洛谷教材写)
623677
tudoulhx楼主2024/5/30 19:09

求dalao帮助(de了3天了)

#include<bits/stdc++.h>
#define N (int)1e5+5
using namespace std;
#define ll long long
ll n,q,nums[N],tree[N<<2],leadtag[N<<2],tolertag[N<<2],opt;//nums原数组,tree线段树数组,leadtag首项lazy标记数组,
//tolertag公差标记数组,opt操作种类 
inline ll ls(ll i){//左孩子 
	return i<<1;
}
inline ll rs(ll i){//右孩子 
	return i<<1|1;
}
inline ll S(ll lead,ll toler,ll len){//等差数列求和公式 
	ll last=lead+toler*(len-1);
	return (lead+last)*len/2;
}
inline void addtag(ll i,ll l,ll r,ll lead,ll toler){//添加标记 
	leadtag[i]+=lead,tolertag[i]+=toler;
	tree[i]+=S(lead,toler,r-l+1);
}
inline void push_up(ll i){//向上更新 
	tree[i]=tree[ls(i)]+tree[rs(i)];
}
void build(ll i,ll pl,ll pr){//根据初始数组建树 
	if(pl==pr){
		tree[i]=nums[pl];
		return ;
	}else{
		int mid=(pl+pr)>>1;
		build(ls(i),pl,mid);
		build(rs(i),mid+1,pr);
	}
}
void push_down(ll i,ll pl,ll pr){//向下更新 
	ll mid=(pl+pr)>>1;
	addtag(ls(i),pl,mid,leadtag[i],tolertag[i]);
	addtag(rs(i),mid+1,pr,leadtag[i]+(mid-pl+1)*tolertag[i],tolertag[i]);
	leadtag[i]=tolertag[i]=0;
}
void update(ll i,ll pl,ll pr,ll L,ll R,ll lead,ll toler){//修改 
	if(L<=pl&&pr<=R){//区间被完全包含,直接改 
		addtag(i,pl,pr,lead,toler);
		return;
	}
	push_down(i,pl,pr);
	ll mid=(pl+pr)>>1;
	if(L<=mid){//左边包含,向左递归 
		update(ls(i),pl,mid,L,R,lead,toler);
	}
	if(R>mid)update(rs(i),mid+1,pr,L,R,lead+(mid-L+1)*toler,toler);//右边包含,向右递归 
	push_up(i);
}
ll query(ll i,ll pl,ll pr,ll L,ll R){
	ll res=0;
	if(L<=pl&&pr<=R){//完全包含,直接返回 
		return tree[i];
	}
	else {
		push_down(i,pl,pr);
		ll mid=(pr+pl)>>1;
		if(L<=mid){//左边包含,向左递归 
			res+=query(ls(i),pl,mid,L,R);
		}
		if(R>mid)res+=query(rs(i),mid+1,pr,L,R);//右边包含,向右递归 
		                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             
		return res;
	}
}
int main(){
//	freopen("无聊的数列.in","r",stdin);
//	freopen("无聊的数列.out","w",stdout);
	cin>>n>>q;
	for(ll i=1;i<=n;i++)cin>>nums[i];
	build(1,1,n);
	for(ll i=1;i<=q;i++){
		ll l;
		cin>>opt>>l;
		if(opt==1){//修改 
			ll lead,toler,r;
			cin>>r>>lead>>toler;
			update(1,1,n,l,r,lead,toler);
		}else if(opt==2)cout<<query(1,1,n,l,l)<<endl;//查询 
	}
}
//10 10
//20 20 20 20 20 20 20 20 20 20
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//1 1 10 1 1
//2 1
2024/5/30 19:09
加载中...