82pts求调(玄关)
查看原帖
82pts求调(玄关)
578251
craft_07楼主2024/3/27 15:16
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
const int N=100003;

int a[N];
int cf[N];
ll tree[N*4];
ll lazy[N*4];

inline int ls(int);
inline int rs(int);
inline int len(int,int);
inline void push_up(int);
void build(int,int,int);
inline void push_down(int,int,int);
inline void add_tag(int,int,int,ll);
void update(int,int,int,int,int,ll);
ll query(int,int,int,int,int);

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cf[i]=a[i]-a[i-1];
	}
	build(1,1,n);
	
	while(m--){
		int opt;
		scanf("%d",&opt);
		switch (opt) {
			case 1 : {
				int l,r,d;
				ll  k;
				scanf("%d%d%lld%d",&l,&r,&k,&d);
				if(l==r){
					update(l,l,1,1,n,k);
					update(l+1,l+1,1,1,n,-k);
					break;
				} 
				update(l,l,1,1,n,k);
				update(l+1,r,1,1,n,d);
				update(r+1,r+1,1,1,n, -(k+d*(r-l)) );
				break;
			}
			case 2 : {
				int p;
				scanf("%d",&p);
				printf("%lld\n",query(1,p,1,1,n));
				break;
			}
		}
	}
	return 0;
}

inline int ls(int x){ return x*2; }
inline int rs(int x){ return x*2+1; }
inline int len(int l,int r){ return r-l+1; }
inline void push_up(int x){
	tree[x]=tree[ls(x)]+tree[rs(x)];
}
void build(int x,int l,int r){
	if(l==r) {
		tree[x]=cf[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	push_up(x);
}
inline void add_tag(int x,int l,int r,ll k){
	lazy[x]=lazy[x]+k;
	tree[x]=tree[x]+k*len(l,r);
}
inline void push_down(int x,int l,int r){
	int mid=(l+r)>>1;
	add_tag(ls(x),l,mid,lazy[x]);
	add_tag(rs(x),mid+1,r,lazy[x]);
	lazy[x]=0;
}
void update(int tl,int tr,int x,int l,int r,ll k){
	if(tl<=l&&r<=tr){
		add_tag(x,l,r,k);
		return ;
	}
	
	push_down(x,l,r);
	int mid=(l+r)>>1;
	if(mid>=tl) update(tl,tr,ls(x),l,mid,k);
	if(mid<tr) update(tl,tr,rs(x),mid+1,r,k);
	push_up(x);
}
ll query(int tl,int tr,int x,int l,int r){
	if(tl<=l&&r<=tr)
		return tree[x];
	ll res=0;
	push_down(x,l,r);
	int mid=(l+r)>>1;
	if(mid>=tl) res= res+query(tl,tr,ls(x),l,mid);
	if(mid<tr) res= res+query(tl,tr,rs(x),mid+1,r);
	return res;
}




2024/3/27 15:16
加载中...