70pts，WA #8 #9 #10,求调

Igunareo @ 2024-02-15 18:32:08

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int x[100005];
int y[400005];
int z[400005];
void build(int now,int l,int r){
    if(l==r){
        y[now]=x[l];
        return;
    }
    int mid=(l+r)/2;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    y[now]=y[now*2]+y[now*2+1];
    return;
}
void up(int now,int l,int r,int fl,int fr,int p){
    y[now]+=1ll*(fr-fl+1)*p;
    if(l==fl&&r==fr){
        z[now*2]+=p;
        z[now*2+1]+=p;
        return;
    }
    int mid=(l+r)/2;
    if(fr<=mid)up(now*2,l,mid,fl,fr,p);
    else if(fl>mid)up(now*2+1,mid+1,r,fl,fr,p);
    else{
        up(now*2,l,mid,fl,mid,p);
        up(now*2+1,mid+1,r,mid+1,fr,p);
    }
    return;
}
int down(int now,int l,int r,int fl,int fr){
    y[now]+=1ll*z[now]*(r-l+1);
    z[now*2]+=z[now];
    z[now*2+1]+=z[now];
    z[now]=0;
    if(l==fl&&r==fr)return y[now];
    int mid=(l+r)/2;
    if(fr<=mid)return down(now*2,l,mid,fl,fr);
    if(fl>mid)return down(now*2+1,mid+1,r,fl,fr);
    return down(now*2,l,mid,fl,mid)+down(now*2+1,mid+1,r,mid+1,fr);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>x[i];
    build(1,1,n);
    while(m--){
        int kind;
        cin>>kind;
        if(kind==1){
            int l,r,p;
            cin>>l>>r>>p;
            up(1,1,n,l,r,p);
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<down(1,1,n,l,r)<<endl;
        }
    }
    return 0;
 } 

by Igunareo @ 2024-02-15 18:42:49

@kevinZ99 你看第二句话

by kevinZ99 @ 2024-02-15 18:45:54

@20220621Soren 我是蒟蒻别管我

by QWQ_123 @ 2024-02-15 18:46:55

@20220621Soren 关掉 O2 后，您的 #8 #9 #10 RE 了，说明是你数组开小了，y,z 都要开到 5 \times 10^5。

by kevinZ99 @ 2024-02-15 18:47:01

@20220621Soren 你要不看看我的

//t:1000ms m:125.00MB
#include <bits/stdc++.h>
#define mid ((l+r)/2)
#define ll long long
using namespace std;
namespace my{
    void IOS(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        return ;
    }
    const int N=1e5+5;
    ll t[(N<<2)];
    ll s[(N<<2)];
    ll a[N];
    int n,q;
    int ls(int x){
        return x*2;
    }
    int rs(int x){
        return x*2+1;
    }
    void push_up(int p){
        s[p]=s[ls(p)]+s[rs(p)];
    }
    void add_tag(int l,int r,int p,ll x){
        s[p]+=(1ll*r-l+1ll)*x;
        t[p]+=x;
    }
    void push_down(int l,int r,int p){
        if(t[p]==0)return ;
        add_tag(l,mid,ls(p),t[p]);add_tag(mid+1,r,rs(p),t[p]);
        t[p]=0;
    }
    void build(int l,int r,int p){
        if(l==r){
            s[p]=a[l];
            return ;
        }
        build(l,mid,ls(p));build(mid+1,r,rs(p));
        push_up(p);
    }
    void add(int l,int r,int L,int R,ll x,int p){
        if(l>R||r<L)return ;
        if(L<=l&&R>=r){
            add_tag(l,r,p,x);
            return ;
        }
        push_down(l,r,p);
        add(l,mid,L,R,x,ls(p));add(mid+1,r,L,R,x,rs(p));
        push_up(p);
    }
    ll ask(int l,int r,int L,int R,int p){
        if(l>R||r<L)return 0ll;
        if(L<=l&&R>=r)return s[p];
        push_down(l,r,p);
        return 1ll*ask(l,mid,L,R,ls(p))+ask(mid+1,r,L,R,rs(p));
    }
    void solve(){
        IOS();
        cin>>n>>q;
        for(int i=1;i<=n;i++)cin>>a[i];
        build(1,n,1);
        while(q--){
            int op,x,y;
            ll k;
            cin>>op;
            if(op==1){
                cin>>x>>y>>k;
                add(1,n,x,y,k,1);
            }
            if(op==2){
                cin>>x>>y;
                cout<<ask(1,n,x,y,1)<<'\n';
            }
        }
    }
}
int main(){
//  freopen("","r",stdin);
//  freopen("","w",stdout);
    int _=1;
    while(_--)my::solve();
    return 0;
}

by Igunareo @ 2024-02-15 18:48:43

@QWQ_123 谢了，我还是第一次知道开O2后数组RE会变WA

by Igunareo @ 2024-02-15 18:57:46

@QWQ_123 不过 5e5 还是有点小，得再多开 3e4 才行（实测）,感谢大佬