蒟蒻求助 样例都过不了

sto_0616allen_orz @ 2023-12-25 23:56:26

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int maxn = 1000006;
int a[100005];
struct tree {
    int l,r,lt,rt,w;
    ll qh;
} c[200015];
int n,m;
int za(int l,int r,int v) {
    if(l==r) {
        c[v]=(tree) {
            l,r,-1,-1,0,a[l]
        };
        return a[l];
    }
    c[v]=(tree) {
        l,r,v<<1,(v<<1)|1,0,za(l,(l+r)>>1,v<<1)+za(((l+r)>>1)+1,r,(v<<1)|1)
    };
    return c[v].qh;
}
int he(int v,int L,int R) {

    c[v].qh+=(c[v].r-c[v].l+1)*c[v].w;
    c[v<<1].w+=c[v].w,c[(v<<1)|1].w+=c[v].w;
    c[v].w=0;
    if(L<=c[v].l&&R>=c[v].r) {
    return c[v].qh;}
    if((c[v].l<=L&&L<=c[v].r)||(R>=c[v].l&&R<=c[v].r)) {
        return he(v<<1,L,R)+he((v<<1)|1,L,R);
    }
    return 0;
}
void jia(int v,int L,int R,int wi) {
    if(L<=c[v].l&&R>=c[v].r) {
        c[v].w+=wi;
        return ;
    }
    if((c[v].l<=L&&L<=c[v].r)||(R>=c[v].l&&R<=c[v].r)) {

        jia(v<<1,L,R,wi);
        jia((v<<1)|1,L,R,wi);
    }
    return ;
}
void dfs(int v) {
    if(v>=n*2) return ;
    cout<<v<<' '<<c[v].w<<endl;
    dfs(v<<1);
    dfs((v<<1)|1);
}
int t,hl,hr,wi;
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    za(1,n,1);
/*  for(int i=0;i<n;i++) cout<<c[n+i].qh <<' ';

        cout<<'\n';*/
    for(int  i=1; i<=m; i++) {
        cin>>t;
        if(t==1) {
            cin>>hl>>hr>>wi;
            jia(1,hl,hr,wi);
            //dfs(1);
        } else {
            cin>>hl>>hr;
            cout<<'#'<<he(1,hl,hr)<<endl;
        }/*
        for(int i=0;i<n;i++) cout<<c[n+i].qh <<' ';cout<<'\n';*/
    }

    return 0;
}

by ArisakaMashiro @ 2023-12-26 00:09:21

你的jia函数应该没问题，问题应该出在he函数上

#include<iostream>
using namespace std;
#define int long long
int st[1145140], lazy[1145140], a[1145140], n, t, ll, rr, d, com;
void build(int l, int r, int where) {
    if (l == r) {
        st[where] = a[l];
        return;
    }
    else {
        int m = l + ((r - l) / 2);
        build(l, m, where * 2);
        build(m + 1, r, where * 2 + 1);
        st[where] = st[where * 2] + st[where * 2 + 1];
    }
}
void add(int l, int r, int nl, int nr, int where, int adnum) {
    if (nl >= l && nr <= r) {
        st[where] += (nr - nl + 1) * adnum;
        lazy[where] += adnum;
        return;
    }
    else {
        int m = nl + ((nr - nl) / 2);
        if (lazy[where] != 0) {
            st[where * 2] += lazy[where] * (m - nl + 1);
            st[where * 2 + 1] += lazy[where] * (nr - m);
            lazy[where * 2] += lazy[where];
            lazy[where * 2 + 1] += lazy[where];
            lazy[where] = 0;
        }
        if (l <= m) {
            add(l, r, nl, m, where * 2, adnum);
        }
        if (r > m) {
            add(l, r, m + 1, nr, where * 2 + 1, adnum);
        }
        st[where] = st[where * 2] + st[where * 2 + 1];
    }
}
int sumup(int l, int r, int nl, int nr, int where) {
    int m = nl + ((nr - nl) / 2);
    int sum = 0;
    if (nl >= l && nr <= r) {
        return st[where];
    }
    if (lazy[where]) {
        st[where * 2] += lazy[where] * (m - nl + 1);
        st[where * 2 + 1] += lazy[where] * (nr - m);
        lazy[where * 2] += lazy[where];
        lazy[where * 2 + 1] += lazy[where];
        lazy[where] = 0;
    }
    if (l <= m) {
        sum += sumup(l, r, nl, m, where * 2);
    }
    if (r > m) {
        sum += sumup(l, r, m + 1, nr, where * 2 + 1);
    }
    return sum;
}
signed main() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, n, 1);
    for (int i = 1; i <= t; i++) {
        cin >> com;
        if (com == 1) {
            cin >> ll >> rr >> d;
            add(ll, rr, 1, n, 1, d);
        }
        else {
            cin >> ll >> rr;
            cout << sumup(ll, rr, 1, n, 1) << '\n';
        }
    }
}

这里贴一份我的，你可以看一下这个sumup函数的思路，应该会有帮助 @sto_0616allen_orz

by sto_0616allen_orz @ 2023-12-26 20:57:23

@Tainaka_Ritsu 谢谢已关