9Pts求调
查看原帖
9Pts求调
1025329
_psycho楼主2023/8/13 09:31
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
#define int long long
int a[N],t[N<<2],lazy[N<<2];
int in[N];
struct TREE{
	void pushdown(int k,int m){
		if(lazy[k]){
			lazy[k<<1]+=lazy[k];
			lazy[k<<1|1]+=lazy[k];
			t[k<<1]+=lazy[k]*(m-(m>>1));
			t[k<<1|1]+=lazy[k]*(m>>1);
			lazy[k]=0;
		}
	}
	void pushup(int k){
		t[k]=t[k<<1]+t[k<<1|1];
	}
	void build(int k,int l,int r){//建树
		if(l==r){
			t[k]=a[l];
		}
		else{
			int m=l+((r-l)>>1);
			build(k<<1,l,m);
			build(k<<1|1,m+1,r);
			pushup(k);
		}
		return  ;
	}
	void updata1(int p,int v,int l,int r,int k){//单点修改
		//p 为要修改的的下标,v 为要修改的权值
		if(l==r){
			t[k]+=v,a[k]+=v;
		}
		else{
			int m=l+((r-l)>>1);
			if(p<=m){
				updata1(p,v,l,m,k<<1);
			}
			else updata1(p,v,m+1,r,k<<1|1);
			pushup(k);
		}
	}
	int query1(int L,int R,int l,int r,int k){//区间查询
		if(L<=l&&r<=R)return t[k];
		else{
			int res=0;
			int m=l+((r-l)>>1);
			if(L<=m){
				res+=query1(L,R,l,m,k<<1);
			}
			if(R>m){
				res+=query1(L,R,m+1,r,k<<1|1);
			}
			return res;
		}
	}
	void updata2(int L,int R,int v,int l,int r,int k){//区间修改
		if(L<=l&&r<=R){
			lazy[k]+=v,t[k]+=v*(r-l+1);
		}
		else{
			int mm=r-l+1;
			pushdown(k,mm);
			int m=l+((r-l)>>1);
			if(L<=m){
				updata2(L,R,v,l,m,k<<1);
			}
			if(R>m){
				updata2(L,R,v,m+1,r,k<<1|1);
			}
			pushup(k);
		}
	}
	int query2(int L,int R,int l,int r,int k){//区间查询
		if(L<=l&&r<=R)return t[k];
		else{
			int res=0;
			int mm=r-l+1;
			pushdown(k,mm);
			int m=l+((r-l)>>1);
			if(L<=m){
				res+=query2(L,R,l,m,k<<1);
			}
			if(R>m){
				res+=query2(L,R,m+1,r,k<<1|1);
			}
			return res;
		}
	}
}T;
main(){
//	freopen("P1438_1.in","r",stdin);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>in[i];
		a[i]=in[i]-in[i-1];
	}
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts(" ");
	T.build(1,1,n);
	while(m--){
		int opt;
		cin>>opt;
		opt--;
		if(!opt){
			int l,r,K,D;
			cin>>l>>r>>K>>D;
			if(r<n)T.updata1(r+1,-1*((r-l)*D+K),1,n,1);
//			for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts(" ");
			T.updata1(l,K,1,n,1);
//			for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts(" ");
			if(l+1<=r)T.updata2(l+1,r,D,1,n,1);
//			for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts(" ");
		}
		else{
			int p;
			cin>>p;
			cout<<T.query2(1,p,1,n,1)<<'\n';	
		}
	}
	return 0;
}
/*
7 60
5 1 7 3 1 2 4
1 2 5 7 2
*/
2023/8/13 09:31
加载中...