样例过了0pt线段树大佬求调
查看原帖
样例过了0pt线段树大佬求调
469213
SugarKite楼主2023/11/4 16:31
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[5000050],tre[5000050],tag[5000050],gc[5000050];
int ls(int x){return 2*x;}
int rs(int x){return 2*x+1;}
int query(int p,int L,int R,int pl,int pr);
void push_up(int p){
//	cout<<"test_push_up:"<<p<<" "<<ls(p)<<" "<<rs(p)<<" "<<tre[ls(p)]<<" "<<tre[rs(p)]<<endl;
	tre[p]=tre[ls(p)]+tre[rs(p)];
}
void add_tag(int p,int pl,int pr,int d,int g){

	tre[p]+=((pr-pl)*g+2*d)*(pr-pl+1)/2;
	tag[p]=d;
	gc[p]=g;

}
void build(int p,int pl,int pr){
//	cout<<"build_test"<<p<<" "<<pl<<" "<<pr<<endl; 
	if(pl==pr){
//		cout<<"test-"<<pl<<" "<<a[pl]<<endl;
		tre[p]=a[pl];
		return ;
	}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
	return ;
}
void push_down(int p,int pl,int pr){
	if(tag[p]){
		int mid=(pl+pr)>>1;
		add_tag(ls(p),pl,mid,tag[p],gc[p]);
		add_tag(rs(p),mid+1,pr,tag[p]+gc[p]*(mid-pl+1),gc[p]);
		tag[p]=0;
		gc[p]=0;
	}
}
void updata(int p,int L,int R,int pl,int pr,int d,int g){
//	cout<<"updata_test"<<p<<" "<<L<<" "<<R<<" "<<pl<<" "<<pr<<" "<<d<<" "<<g<<endl; 
	if(pl>=L&&pr<=R){
		add_tag(p,pl,pr,d,g);
		return ;
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(mid>=L)updata(ls(p),L,R,pl,mid,d,g);
	if(mid<R)updata(rs(p),L,R,mid+1,pr,d+g*(mid-pl+1),g);
	push_up(p);
	return ;
}
int query(int p,int L,int R,int pl,int pr){
	if(pl>=L&&pr<=R)return tre[p];
	push_down(p,pl,pr);
	int res=0;
	int mid=(pl+pr)>>1;
	if(mid>=L)res+=query(ls(p),L,R,pl,mid);
	if(mid<R)res+=query(rs(p),L,R,mid+1,pr);
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	while(m--){
		int op,l,r;
		scanf("%d",&op);
		if(op==1){
			int d,g;
			scanf("%d%d%d%d",&l,&r,&d,&g);
			updata(1,l,r,1,n,d-g*(l-1),g);
		}
		else{
			int x;
			scanf("%d",&x); 
			printf("%d\n",query(1,x,x,1,n));
		}
	}

	return 0;
}

2023/11/4 16:31
加载中...