社区讨论
只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 条回复,欢迎继续交流。
正在加载回复...