45pts 求调QAQ
查看原帖
45pts 求调QAQ
1067741
Andyxz楼主2024/10/10 17:45
#include<iostream>
#include<cstdio>
#define ll long long
#define MAXN 1000001
using namespace std;
ll b[MAXN];
ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x){
	return x<<1;
}
inline ll rs(ll y){
	return y<<1|1;
}
inline void f(ll p,ll l,ll r,ll k){
	tag[p]=tag[p]+k;
	ans[p]=ans[p]+k*(r-l+1);
}//更新子点
void in(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
	scanf("%lld",&b[i]);
	b[1]=a[1];
	for(ll i=2;i<=n;i++){
		a[i]=b[i]-b[i-1];//差分数列
	}
	return;
}
inline void push_up(ll p){
	ans[p]=ans[ls(p)]+ans[rs(p)];
}
inline void push_down(ll p,ll l,ll r){
	ll mid=(l+r)>>1;
	f(ls(p),l,mid,tag[p]);
	f(rs(p),mid+1,r,tag[p]);
	tag[p]=0;
}

void build(ll p,ll l,ll r){
	tag[p]=0;
	if(l==r){
		ans[p]=a[l];return;
	}
	ll mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}

inline void update(ll l1,ll r1,ll l,ll r,ll p,ll k){
	if(l1<=l&&r<=r1){
		ans[p]+=k*(r-l+1);
		tag[p]+=k;//懒标记
		return;
	}
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(l1<=mid) update(l1,r1,l,mid,ls(p),k);
	if(r1>mid) update(l1,r1,mid+1,r,rs(p),k);
	push_up(p);
}
ll query(ll x,ll y,ll l,ll r,ll p){
	ll res=0;
	if(x<=l&&y>=r){
		return ans[p];
	}
	ll mid=(l+r)>>1;
	push_down(p,l,r);
	if(x<=mid) res+=query(x,y,l,mid,ls(p));
	if(y>mid) res+=query(x,y,mid+1,r,rs(p));
	return res;
}
 //上面是线段树的板子
int main(){
	ll a1,b,c,d,e,f,g;
	in();
	build(1,1,n);
	while(m--){
		scanf("%lld",&a1);
		if(a1==1){
				scanf("%lld%lld%lld%lld",&b,&c,&d,&g);
				update(b,b,1,n,1,d);//区间头部加d
				update(c+1,c+1,1,n,1,-g*(c-b)-d);//区间后面一个数减
				update(b+1,c,1,n,1,g);//区间中的数都加上g

				}
		else{
				scanf("%lld",&e);
				printf("%lld\n",query(1,e,1,n,1));//获取数列中第e个数的值
			}
		}
	return 0;
}
2024/10/10 17:45
加载中...