九分不理解为什么出不来负数
查看原帖
九分不理解为什么出不来负数
1420936
Sparkle_ovo楼主2024/9/17 23:13
#include<iostream>
#include<string.h>
#define LL long long int
using namespace std;
LL a[100010],tree[200010],lazy[200010],b[200010];
int n,m;
void push(int pos,int l,int r) {
	int mid=(l+r)>>1,ls=pos<<1,rs=pos<<1|1,len=r-l+1;
	tree[ls]+=(mid-l+1)*lazy[pos];
	tree[rs]+=(r-mid)*lazy[pos];
	lazy[rs]+=lazy[pos];
	lazy[ls]+=lazy[pos];
	lazy[pos]=0;
	return;
}
void change(int pos,int l,int r,int cl,int cr,LL val) {
	int mid=(l+r)>>1,ls=pos<<1,rs=pos<<1|1;
	if(l==r) {
		tree[pos]+=val;
		return ;
	}
	if(cl<=l&&r<=cr) {
		lazy[pos]+=val;
		tree[pos]+=(r-l+1)*val;
		return ;
	}
	push(pos,l,r);
	if(cl<=mid)change(ls,l,mid,cl,cr,val);
	if(cr>mid)change(rs,mid+1,r,cl,cr,val);
	tree[pos]=tree[ls]+tree[rs];
	return;
}
LL ask(int pos,int l,int r,int al,int ar) {
	int mid=(l+r)>>1,ls=pos<<1,rs=pos<<1|1;
	LL ans=0;
	if(l==r) {
		return tree[pos];
	}
	if(al<=l&&ar>=r) {
		return tree[pos];
	}
	push(pos,l,r);
	if(al<=mid) ans+=ask(ls,l,mid,al,ar);
//	ans+=tree[ls];
//	if(p<=mid) ans+=ask(ls,l,mid,p);
	if(ar>mid) ans+=ask(rs,mid+1,r,al,ar);
	return ans;
}
void build(int pos,int l,int r) {
	if(l==r) {
		tree[pos]=a[l];
		return;
	}
	int mid=(l+r)>>1,ls=pos<<1,rs=pos<<1|1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tree[pos]=tree[ls]+tree[rs];
	return;
}
int main() {
	memset(tree,0,sizeof(tree));
//	memset(a,0,sizeof(a));
	memset(lazy,0,sizeof(lazy));
	cin>>n>>m;
	int opt;
	for(int i=1; i<=n; i++) {
		scanf("%d",&b[i]);
	}
	a[1]=b[1];
	for(int i=2; i<=n; i++) {
		a[i]=b[i]-b[i-1];
	}
	build(1,1,n);
	int opa;
	for(int i=1; i<=m; i++) {
		scanf("%d",&opt);
		if(opt==1) { //change
			int l,r;
			LL k,d;
			scanf("%d %d %lld %lld",&l,&r,&k,&d);
//			if(l!=1)
			change(1,1,n,l,l,k);//头部更改
			if(l<r)change(1,1,n,l+1,r,d);//区间更改
//			int len=r-l+1;
			if(r<n)change(1,1,n,r+1,r+1,-(k+d*(r-l))); //尾部更改
		}
		if(opt==2) { //ask
			int p;
			scanf("%d",&p);
//			opa=ask(1,1,n,1,p);
//			cout<<opa<<endl;
			cout<<ask(1,1,n,1,p)<<endl;
		}
	}
	system("pause");
	return 0;
}
2024/9/17 23:13
加载中...