社区讨论
WA后三个点,实在想不出来了
P3372【模板】线段树 1参与者 3已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mi86inhk
- 此快照首次捕获于
- 2025/11/21 09:26 4 个月前
- 此快照最后确认于
- 2025/11/21 09:26 4 个月前
RT,求助大佬
使用二进制计算子节点坐标
CPP使用二进制计算子节点坐标
#include <cstdio>
#define N 100001
using namespace std;
long long a[N];
struct Node{
long long l,r;
long long tag,sum;
}t[N<<2];
//============================
//维护数值
void pushup(long long rt){
t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
}
void pushdown(long long rt){
if(t[rt].tag){
t[rt<<1].tag+=t[rt].tag;
t[rt<<1].sum+=t[rt].tag*(t[rt<<1].r-t[rt<<1].l+1);
t[rt<<1|1].tag+=t[rt].tag;
t[rt<<1|1].sum+=t[rt].tag*(t[rt<<1|1].r-t[rt<<1|1].l+1);
t[rt].tag=0;
}
}
//============================
//递归建树
void build(long long rt,long long l,long long r){
t[rt].l=l;t[rt].r=r;
if(l==r){
t[rt].tag=0;
t[rt].sum=a[l];
return;
}
long long mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
//============================
//区间修改
void seg_modify(long long rt,long long l,long long r,long long c){
if(l<=t[rt].l&&t[rt].r<=r){
t[rt].tag+=c;
t[rt].sum+=c*(t[rt].r-t[rt].l+1);
return;
}
pushdown(rt);
long long mid=(t[rt].l+t[rt].r)>>1;
if(l<=mid) seg_modify(rt<<1,l,r,c);
if(mid<r) seg_modify(rt<<1|1,l,r,c);
pushup(rt);
}
//============================
//查询
int query(long long rt,long long l,long long r){
if(l<=t[rt].l&&t[rt].r<=r){
return t[rt].sum;
}
pushdown(rt);
long long ret=0;
long long mid=(t[rt].l+t[rt].r)>>1;
if(l<=mid) ret+=query(rt<<1,l,r);
if(mid<r) ret+=query(rt<<1|1,l,r);
pushup(rt);
return ret;
}
//============================
long long n,m;
int main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++){
int t;
long long t_l,t_r,t_c;
scanf("%d",&t);
if(t==1){
scanf("%lld %lld %lld",&t_l,&t_r,&t_c);
seg_modify(1,t_l,t_r,t_c);
// mod();
}
if(t==2){
scanf("%lld %lld",&t_l,&t_r);
long long ans=query(1,t_l,t_r);
printf("%lld \n",ans);
}
}
return 0;
}
回复
共 9 条回复,欢迎继续交流。
正在加载回复...