70pts求调
查看原帖
70pts求调
1071426
shx2011楼主2025/1/19 23:55

我开longlong了啊???

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const LL N=1e5+10;
LL tree[4*N],a[N],add[N],n; 
void build(LL l,LL r,LL k){//l:左端点 r:右端点 k:节点编号
    if(l==r){//如果是叶子节点(叶子节点的左右端点相等,即长度为1)
        tree[k]=a[l];//赋值
        return;
    }
    
    LL mid=(l+r)>>1;//取中间值
    build(l,mid,2*k);//拆分左子树
    build(mid+1,r,2*k+1);//拆分右子树
    tree[k]=tree[2*k]+tree[2*k+1];//pushup:回溯时利用子节点更新父节点(此处维护最大值)
}

void change(LL k,LL l,LL r,LL v){//修改一个节点 
	tree[k]+=v*(r-l+1);//修改值 
	add[k]+=v;//标记 
}

void down(LL k,LL l,LL r){//标记下放 
	if(add[k]!=0){
		LL mid=(l+r)>>1;
		change(k*2,l,mid,add[k]);//下放到左孩子 
		change(k*2+1,mid+1,r,add[k]);//下放到右孩子 
		add[k]=0;//父节点标记清空 
	}
}
void update(LL k,LL l,LL r,LL x,LL y,LL v){//把节点p的值改为x l:左端点 r:右端点 k:当前节点编号
    if(l>=x && r<=y){
    	change(k,l,r,v);
    	return;
	}
	down(k,l,r);
    LL mid=(l+r)>>1;
    if(x<=mid) update(2*k,l,mid,x,y,v);//左子树 
    if(y>mid) update(2*k+1,mid+1,r,x,y,v);//右子树 
    tree[k]=tree[2*k]+tree[2*k+1];
}

LL quary(LL k,LL l,LL r,LL x,LL y){//查询x到y的区间最大值
     if(l>=x && r<=y){//如果当前的区间完全包含在查询区间中时,不需要继续递归
        return tree[k];
     }
	 down(k,l,r); 
     LL mid=(l+r)>>1;
     LL res=0;
     if(x<=mid){//左区间有覆盖
        res+=quary(2*k,l,mid,x,y);
     }
     if(y>mid){//右区间有覆盖
        res+=quary(2*k+1,mid+1,r,x,y);
     }

     return res;
}

LL m;
int main(){
	cin>>n>>m;
	for(LL i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(LL i=1;i<=m;i++){
		LL t;
		cin>>t;
		if(t==1){
			LL x,y,k;
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}else{
			LL x,y;
			cin>>x>>y;
			cout<<quary(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}

2025/1/19 23:55
加载中...