求助,P3372的线段树模板写炸了

回复帖子

@ztx666  2020-08-01 21:11 回复

rt

AC4个点,WA6个点

题目:https://www.luogu.com.cn/problem/P3372

测评信息:https://www.luogu.com.cn/record/36199097

自己调了亿下程序,看了亿下题解,找不出什么跟正解的区别和错误(因为我太弱了qwq),所以特意求助大佬们。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef long long ll;
ll n,m,a[MAXN],tree[MAXN*4],lasy[MAXN*4];
void build(ll rt,ll l,ll r){
    if(l==r){
        tree[rt]=a[l];
    }else{
        ll mid=(l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
        tree[rt]=tree[rt*2]+tree[rt*2+1];
    }
}
void push_down(ll rt,ll l,ll r){
    ll mid=(l+r)/2;
    if(lasy[rt]){
        lasy[rt*2]+=lasy[rt];
        lasy[rt*2+1]+=lasy[rt];
        tree[rt*2]+=lasy[rt]*(mid-l+1);
        tree[rt*2+1]+=lasy[rt]*(r-mid);
        lasy[rt]=0;
    }
}
ll query(ll rt,ll l,ll r,ll L,ll R){
    if(L<=l&&R>=r){
        return tree[rt];
    }else{
        ll ret=0,mid=(l+r)/2;
        push_down(rt,l,r);
        if(mid>=L){
            ret+=query(rt*2,l,mid,L,R);
        }
        if(mid+1<=R){
            ret+=query(rt*2+1,mid+1,r,L,R);
        }
        return ret;
    }
}
void add(ll rt,ll l,ll r,ll L,ll R,ll k){
    if(L<=l&&R>=r){
        tree[rt]+=(r-l+1)*k;
        lasy[rt]+=k;
    }else{
        ll mid=(l+r)/2;
        push_down(rt,l,r);
        if(mid>=L){
            add(rt*2,l,mid,L,R,k);
        }
        if(mid+1<=R){
            add(rt*2+1,mid+1,r,L,R,k);
        }
        tree[rt]=tree[rt*2]+tree[rt*2+1];
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    build(1,1,n);
    for(ll i=1;i<=n;i++){
        ll op;
        scanf("%lld",&op);
        if(op==1){
            ll x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,1,n,x,y,k);
        }else if(op==2){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

@CDsidi @Laoyin @lxhcr1 救救juruo吧qwq

@Keith_2006  2020-08-01 21:19 回复 举报
    for(ll i=1;i<=n;i++){
        ll op;
        scanf("%lld",&op);
        if(op==1){
            ll x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,1,n,x,y,k);
        }else if(op==2){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。