线段树0pts求调
查看原帖
线段树0pts求调
1054608
kanzaki楼主2023/11/8 21:04

思路是同时维护首项和公差,lzyx表示首项,lzyy表示公差,求大佬告知错误原因

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
long long a[maxn],w[maxn*4],lzyx[maxn*4],lzyy[maxn*4];
void pushup(int u){
	w[u]=w[u*2]+w[u*2+1];
}
void build(int u,int L,int R){
	if(L==R){
		w[u]=a[L];
		return ;
	}
	else {
		int M=(R+L)/2;
		build(u*2,L,M),build(u*2+1,M+1,R);
		pushup(u);
	}
}
bool inrange(int L,int R,int l,int r){
	return (l<=L)&(R<=r);
}
bool outofrange(int L,int R,int l,int r){
	return (L>r)||(R<l);
}
long long s(int ax,int ay,int len){
	long long an=ax+ay*(len-1);
	return (ax+an)*len/2;
}
void maketag(int u,int len,int add_x,int add_y){
	w[u]+=s(add_x,add_y,len);
	lzyx[u]+=add_x;
	lzyy[u]+=add_y;
}
void pushdown(int u,int L,int R){
	int M=(R+L)/2;
	maketag(u*2,M-L+1,lzyx[u],lzyy[u]);
	maketag(u*2+1,R-M,lzyx[u],lzyy[u]);
	lzyx[u]=0,lzyy[u]=0;
}
long long query(int u,int L,int R,int p){
	if(L==R) return w[u];
	int M=(R+L)/2;
	pushdown(u,L,R);
	if(M>=p) return query(u*2,L,M,p);
	else return query(u*2+1,M+1,R,p);
}
void update(int u,int L,int R,int l,int r,long long x,long long y){
	if(inrange(L,R,l,r)) maketag(u,R-L+1,x,y);
	else if(!outofrange(L,R,l,r)){
		int M=(R+L)/2;
		pushdown(u,L,R);
		update(u*2,L,M,l,r,x,y);
		update(u*2+1,M+1,R,l,r,x,y);
		pushup(u);
	}
}
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op;
		cin>>op;
		if(op==1){
			int l,r,k,d;
			cin>>l>>r>>k>>d;
			update(1,1,n,l,r,k,d);
		}
		else if(op==2){
			int p;
			cin>>p;
			cout<<query(1,1,n,p)<<endl;
		}
	}
	return 0;
}
2023/11/8 21:04
加载中...