求调线段树维护首项和公差样例可过0pts码风良好
查看原帖
求调线段树维护首项和公差样例可过0pts码风良好
1072502
Zskioaert1106楼主2025/2/3 13:11

rt,线段树维护等差数列的首项和公差过了样例但爆零。线段树大部分是照着深进写的。

#include<iostream>
#define int long long
using namespace std;
const int N=1e5+1;
int n,m,a[N],lzyK[N<<2]/*首项*/,lzyD[N<<2]/*公差*/,s[N<<2];
void pushup(int u){
	s[u]=s[u<<1]+s[u<<1|1];
}
void build(int u,int l,int r){//建树
	if(l==r)s[u]=a[l];
	else{
		build(u<<1,l,l+r>>1),build(u<<1|1,(l+r>>1)+1,r);
		pushup(u);
	}
}
long long S(int k,int d,int len){//求等差数列和
	return (k+k+d*(len-1))*len>>1;
}
void maketag(int u,int l,int r,int k,int d){//标记
	lzyK[u]+=k,lzyD[u]+=d;
	s[u]+=S(k,d,r-l+1);
}
void pushdown(int u,int l,int r){//下放
	maketag(u<<1,l,l+r>>1,lzyK[u],lzyD[u]);
	maketag(u<<1|1,(l+r>>1)+1,r,lzyK[u]+lzyD[u]*((l+r>>1)-l),lzyD[u]);
	lzyK[u]=0,lzyD[u]=0;
}
void update(int u,int L,int R,int l,int r,int k,int d){
	if(l<=L&&R<=r)//包含
		maketag(u,L,R,k,d);
	else if(l<=R&&L<=r){//重合
		pushdown(u,L,R);
		update(u<<1,L,L+R>>1,l,r,k,d);
		update(u<<1|1,(L+R>>1)+1,R,l,r,k+d*((L+R>>1)-L),d);
		pushup(u);
	}
}
long long query(int u,int l,int r,int p){
	if(l<=p&&p<=r){//包含
		if(l==r)return s[u];
		pushdown(u,l,r);
		return query(u<<1,l,l+r>>1,p)+query(u<<1|1,(l+r>>1)+1,r,p);
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(short opt;m--;){
		cin>>opt;
		if(opt==1){
			int l,r,k,d;
			cin>>l>>r>>k>>d;
			update(1,1,n,l,r,k,d);
		}
		else if(opt==2){
			int p;
			cin>>p;
			cout<<query(1,1,n,p)<<'\n';
		}
	}
	return 0;
}
2025/2/3 13:11
加载中...