求助,线段树9pts
查看原帖
求助,线段树9pts
1073661
dabenBbx楼主2024/3/4 18:42
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2000005;
int n,m;
int a[maxn],w[maxn*4],lx[maxn*4],ry[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;
	}
	int mid=(l+r)>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}
bool inrange(int l1,int r1,int l2,int r2){
	return (l1>=l2)&&(r1<=r2);
}
bool outofrange(int l1,int r1,int l2,int r2){
	return (l1>r2)||(r1<l2);
}
int s(int ax,int ay,int len){
	int an=ax+ay*(len-1);
	return (ax+an)*len/2;
}
void make(int u,int l,int r,int addx,int addy){
	lx[u]+=addx;
	ry[u]+=addy;
//	cout<<s(addx,addy,r-l+1)<<'\n';
//	cout<<addx<<' '<<addy<<'\n';
	w[u]+=s(addx,addy,r-l+1);
}
void pushdown(int u,int l,int r){
	int mid=(l+r)>>1;
	make(u*2,l,mid,lx[u],ry[u]);
	make(u*2+1,mid+1,r,lx[u]+(mid-l+1)*ry[u],ry[u]);
	lx[u]=ry[u]=0;
}
int query(int u,int l1,int r1,int l2,int r2){
	if(inrange(l1,r1,l2,r2)){
		return w[u];
	}else
	if(!outofrange(l1,r1,l2,r2)){
		int mid=(l1+r1)>>1;
		pushdown(u,l1,r1);
		return query(u*2,l1,mid,l2,r2)+query(u*2+1,mid+1,r1,l2,r2);
	}else
	  return 0;
}
void update(int u,int l1,int r1,int l2,int r2,int k,int d){
//	cout<<k<<' '<<d<<'\n';
	if(inrange(l1,r1,l2,r2)){
		make(u,l1,r1,k,d);
		return;
	}else
	if(!outofrange(l1,r1,l2,r2)){
		pushdown(u,l1,r1);
		int mid=(l1+r1)>>1;
		update(u*2,l1,mid,l2,r2,k,d);
		update(u*2+1,mid+1,r1,l2,r2,k+(mid-l1)*d,d);
		pushup(u);
	}
}
signed main(){
//	freopen("1.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	    cin>>a[i];
	build(1,1,n);
	while(m--){
		int op,l,r,k,d;
		cin>>op;
		if(op==1){
			cin>>l>>r>>k>>d;
			update(1,1,n,l,r,k,d);
		}else{
			cin>>l;
			cout<<query(1,1,n,l,l)<<"\n";
		}
	}
	return 0;
}

附 hack:

6 2
1 -1 4 -5 -1 4
1 3 4 -1 -1
2 4
2024/3/4 18:42
加载中...