无差分纯线段树全WA求调
查看原帖
无差分纯线段树全WA求调
877829
Anythingispossible楼主2024/9/1 00:02
#include<cstdio>
#define int long long
#define le x<<1
#define ri x<<1|1
using namespace std;
const int N=1e5+10;
int n,m,a[N];
struct sai{
	int l,r,val,laz1,laz2,op;//laz1维护公差 laz2维护首项 
}tr[N<<2];
void push_up(int x){
	tr[x].val=tr[le].val+tr[ri].val;
}
void build(int l,int r,int x){
	tr[x].l=l,tr[x].r=r;
	if(l==r){
		tr[x].val=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,le);
	build(mid+1,r,ri);
	push_up(x);
}
void push_down(int x){
	if(tr[x].laz1!=0){
		tr[le].laz1+=tr[x].laz1;
		tr[ri].laz1+=tr[x].laz1;
		tr[le].val+=(tr[le].r-tr[le].l+1)*(tr[le].r-tr[le].l)/2;
		tr[ri].val+=(tr[ri].r-tr[ri].l+1)*(tr[ri].r-tr[ri].l)/2;
	}
	if(tr[x].op==1){
		tr[le].laz2+=tr[x].laz2;
		tr[ri].laz2+=tr[x].laz2+(tr[le].r-tr[le].l)*tr[x].laz1;	
		tr[le].val+=tr[le].laz2*(tr[le].r-tr[le].l+1);
		tr[ri].val+=tr[ri].laz2*(tr[ri].r-tr[ri].l+1);
		tr[le].op=1;
		tr[ri].op=1;
		tr[x].op=0;
	}
	tr[x].laz1=0,tr[x].laz2=0;
}
void update(int l,int r,int x,int k,int d){
	if(tr[x].l>=l&&tr[x].r<=r){
		tr[x].laz1+=k;
		tr[x].laz2+=d+(tr[x].l-l)*tr[x].laz1;
		tr[x].op=1;
		tr[x].val+=tr[x].laz2*(tr[x].r-tr[x].l+1)+tr[x].laz1*(tr[x].r-tr[x].l+1)*(tr[x].r-tr[x].l)/2;
		return ;
	}
	push_down(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) update(l,r,le,k,d);
	if(r>mid) update(l,r,ri,k,d);
	push_up(x);
} 
int query(int l,int r,int x){
	if(tr[x].l>=l&&tr[x].l<=r){
		return tr[x].val;
	}
	push_down(x);
	int mid=(tr[x].l+tr[x].r)>>1,res=0;
	if(l<=mid) res+=query(l,r,le);
	if(r>mid) res+=query(l,r,ri);
	return res;
}
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op;
		scanf("%lld",&op);
		if(op==1){
			int A,B,K,D;
			scanf("%lld %lld %lld %lld",&A,&B,&K,&D);
			update(A,B,1,K,D);
		}
		else{
			int pos;
			scanf("%lld",&pos);
			printf("%lld\n",query(pos,pos,1));
		}
	}
	return 0;
} 
2024/9/1 00:02
加载中...