91pts,已开long long,求大佬!
查看原帖
91pts,已开long long,求大佬!
640477
biophitma_wby楼主2024/11/18 21:00

如标题所言,long long都开了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m;
int opt,l,r,p,K,D;
struct Tree{
	int ls,rs;
	ll val,a1,d;
}tree[N<<2];
void pushdown(int k){
	ll a1=tree[k].a1;int d=tree[k].d;
	ll a1_tmp=a1;int len=tree[2*k].rs-tree[2*k].ls+1;
	tree[2*k].val+=a1_tmp*len+((len-1)*len*d)/2;
	tree[2*k].a1+=a1_tmp,tree[2*k].d+=d;
	a1_tmp=a1+(tree[2*k+1].ls-tree[k].ls)*d;len=(tree[2*k+1].rs-tree[2*k+1].ls+1);
	tree[2*k+1].val+=a1_tmp*len+((len-1)*len*d)/2;
	tree[2*k+1].a1+=a1_tmp,tree[2*k+1].d+=d;
	tree[k].a1=tree[k].d=0;
}
void build(int k,int l,int r){
	tree[k].ls=l,tree[k].rs=r;
	if(l==r){
		scanf("%lld",&tree[k].val);
		tree[k].a1=tree[k].d=0;
		return;
	}
	int mid=(l+r)>>1;
	build(2*k,l,mid);
	build(2*k+1,mid+1,r);
}
void add_interval(int k,int l,int r,int a1,int d){
	if(l<=tree[k].ls&&tree[k].rs<=r){
		ll a1_tmp=a1+(tree[k].ls-l)*d;
		int len=tree[k].rs-tree[k].ls+1;
		//printf("%d %d %d\n",a1_tmp,len,len*a1_tmp+((len-1)*len*d)/2);
		tree[k].val+=len*a1_tmp+((len-1)*len*d)/2;
		tree[k].a1+=a1_tmp,tree[k].d+=d;
		return;
	}
	if(tree[k].a1||tree[k].d)pushdown(k);
	int mid=(tree[k].ls+tree[k].rs)>>1;
	if(l<=mid)add_interval(2*k,l,r,a1,d);
	if(mid<r)add_interval(2*k+1,l,r,a1,d);
}
ll ask_point(int k,int x){
	if(tree[k].ls==tree[k].rs){
		return tree[k].val;
	}
	if(tree[k].a1||tree[k].d)pushdown(k);
	int mid=(tree[k].ls+tree[k].rs)>>1;
	if(x<=mid)return ask_point(2*k,x);
	else return ask_point(2*k+1,x);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	while(m--){
		scanf("%d",&opt);
		if(opt==1){
			scanf("%d%d%d%d",&l,&r,&K,&D);
			add_interval(1,l,r,K,D);
		}else{
			scanf("%d",&p);
			printf("%lld\n",ask_point(1,p));
		}
		/*
		for(int i=1;i<=n;i++){
			printf("%d ",ask_point(1,i));
		}printf("\n");*/
	}
	return 0;
}
2024/11/18 21:00
加载中...