社区讨论

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 条回复,欢迎继续交流。

正在加载回复...