社区讨论

只AC了三个点,求助

P3372【模板】线段树 1参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi61jeul
此快照首次捕获于
2025/11/19 21:31
4 个月前
此快照最后确认于
2025/11/21 00:00
4 个月前
查看原帖
以下为源代码
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
long long a[N],tree[2*N],tag[2*N];
void build(int left,int right,int now){
	if(left==right){
		tree[now]=a[left];
		return ;
	}
	int mid=(left+right)/2;
	build(left,mid,now*2);
	build(mid+1,right,now*2+1);
	tree[now]=tree[now*2]+tree[now*2+1];
	return ;
}
void add(int l,int r,int left,int right,long long num,int now){
	if(l==left&&r==right){
		tag[now]+=num;
		return ;
	}
	int mid=(left+right)/2;
	tree[now]+=num*(r-l+1);
	if(r<=mid){
		add(l,r,left,mid,num,now*2);
		return ;
	}
	if(l>mid){
		add(l,r,mid+1,right,num,now*2+1);
		return ;
	}
	add(l,mid,left,mid,num,now*2);
	add(mid+1,r,mid+1,right,num,now*2+1);
	return ;
}
int read(int l,int r,int left,int right,int now){
	if(l==left&&r==right){
		return tree[now]+tag[now]*(r-l+1);
	}
	int mid=(left+right)/2;
	tag[now*2]+=tag[now];
	tag[now*2+1]+=tag[now];
	tree[now]+=tag[now]*(right-left+1);
	tag[now]=0;
	if(r<=mid){
		return read(l,r,left,mid,now*2);
	}
	if(l>mid){
		return read(l,r,mid+1,right,now*2+1);
	}
	return read(l,mid,left,mid,now*2)+read(mid+1,r,mid+1,right,now*2+1);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int x,p1,p2,p3;
		cin>>x;
		if(x==1){
			cin>>p1>>p2>>p3;
			add(p1,p2,1,n,p3,1);
		}else{
			cin>>p1>>p2;
			cout<<read(p1,p2,1,n,1)<<endl;
		}
	}
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...