求助纯线段树,无差分,只为证明其正确性而求调
查看原帖
求助纯线段树,无差分,只为证明其正确性而求调
572587
cmrhhh楼主2024/4/27 21:33
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+10;
int n,m,opt,a[MAXN];
struct Lazy{
	int k,d;
}lazy[MAXN<<2];
struct Tree{
	int l,r,sum;
}tr[MAXN<<2]; 
void pushup(int x){
	tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
}
void build(int x,int l,int r){
	tr[x]=(Tree){l,r,a[l]};
	if(l==r)return ;
	int m=(l+r)>>1;
	build(x<<1,l,m);
	build(x<<1|1,m+1,r);
	pushup(x);
}
void pushdown(int x){
	lazy[x<<1].k+=lazy[x].k; 
	lazy[x<<1].d+=lazy[x].d;
	lazy[x<<1|1].k+=lazy[x].k+lazy[x].d*(tr[x<<1].r-tr[x<<1].l+1); 
	lazy[x<<1|1].d+=lazy[x].d;
	tr[x<<1].sum+=(2*lazy[x].k+lazy[x].d*(tr[x<<1].r-tr[x<<1].l))*(tr[x<<1].r-tr[x<<1].l+1)>>1;
	tr[x<<1|1].sum+=(2*lazy[x].k+2*lazy[x].d*(tr[x<<1].r-tr[x<<1].l+1)+lazy[x].d*(tr[x<<1|1].r-tr[x<<1|1].l))*(tr[x<<1|1].r-tr[x<<1|1].l+1)>>1;
	lazy[x]=(Lazy){0,0};
}

void upd(int x,int l,int r,int k,int d){
	if(l<=tr[x].l&&tr[x].r<=r){
		lazy[x].k+=k;
		lazy[x].d+=d;
		tr[x].sum+=(2*lazy[x].k+(tr[x].r-tr[x].l)*lazy[x].d)*(tr[x].r-tr[x].l+1)>>1;
		return ;
	}
	int m=(tr[x].l+tr[x].r)>>1;
	pushdown(x);
	if(l<=m)upd(x<<1,l,r,k,d);
	if(m<r)upd(x<<1|1,l,r,k+(m-l+1)*d,d);
	pushup(x);
	
}

int query(int x,int l,int r){
	if(l<=tr[x].l&&tr[x].r<=r)return tr[x].sum;
	int m=(tr[x].l+tr[x].r)>>1;
	pushdown(x);int s=0;
	if(l<=m)s+=query(x<<1,l,r);
	if(m<r)s+=query(x<<1|1,l,r);
	return s;
}

signed main(){
	int l,r,K,D,p;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&K,&D);
			upd(1,l,r,K,D);
		}
		if(opt==2){
			scanf("%lld",&p);
			printf("%lld\n",query(1,p,p));
		}
	}
	
	
	return 0;
}

/*

5 6
1 2 3 4 5
1 2 5 3 4
1 4 5 3 2
2 5
1 3 4 6 9
1 1 4 3 2
2 4



*/
2024/4/27 21:33
加载中...