Eltaos_xingyu @ 2023-07-18 17:46:56

#include <bits/stdc++.h>
using namespace std;
int a[1000001], b[100001], ld[100001];

long long xds(int l, int r, int now) {
    if (l == r) {
        a[now] = b[l];
        return a[now];
    }
    long long mid = (l + r) / 2;
    a[now] = xds(l, mid, now * 2) + xds(mid + 1, r, now * 2 + 1);
    return a[now];
}
void push_down(int l,int r,int now){
    if(l==r){
        return;
    }
    if(ld[now]){
        a[now*2]=a[now*2]+((r+l)/2-l+1)*ld[now];
        a[now*2+1]=a[now*2+1]+(r-(r+l)/2)*ld[now];
        if(r-l>2)ld[now*2]=ld[now];
        if(r-l>3)ld[now*2+1]=ld[now];
        ld[now]=0;
    }
}
long long getsum(int l, int r, int sl, int sr, int now) {
    if (l == sl && r == sr){
        return a[now];
    }
    push_down(l,r,now);
    long long sum = 0;
    int mid = (l + r) / 2;
    if (sl <= mid)
        sum += getsum(l, mid, sl, min(sr, mid), now * 2);
    if (sr > mid)
        sum += getsum(mid + 1, r, max(sl, mid + 1), sr, now * 2 + 1);
    return sum;
}

void in2_up(int l, int r, int now, int num) {
    a[now] += num;
    if (now == 1)
        return;
    if (now % 2)
        in2_up(2 * l - r - 2, r, (now - 1) / 2, num);
    else
        in2_up(l, 2 * r - l, now / 2, num);
    return;
}

//mid=(l+r)/2=>l+r=2mid=>l=2mid-r=>l=2(mid+1)-r-2
void inner_up(int l, int r, int now, long long num) {
    a[now]+=num;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    inner_up(l, mid, now * 2, num), inner_up(mid + 1, r, now * 2 + 1, num);
    return;
}

void update(int l, int r, int sl, int sr, int now, int num) {
    if (l == sl && r == sr) {
        in2_up(l, r, now, (r-l+1)*num);
        if(l!=r)ld[now]=num;
        return;
    }
    int mid = (l + r) / 2;
    if (sl <= mid)
        update(l, mid, sl, min(sr, mid), now * 2, num);
    if (sr > mid)
        update(mid + 1, r, max(sl, mid + 1), sr, now * 2 + 1, num);
    return;
}

int main() {
    int n = 0, m = 0, temp = 0, t1 = 0, t2 = 0, t3 = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    xds(1, n, 1);
    for (int i = 1; i <= m; i++) {
        cin >> temp;
        if (temp == 1) {
            cin >> t1 >> t2 >> t3;
            update(1, n, t1, t2, 1, t3);
        } else {
            cin >> t1 >> t2;
            cout << getsum(1, n, t1, t2, 1) << endl;
//          for(int ii=1;ii<=2*n+1;ii++)cout<<a[ii]<<" ";
//          cout<<endl;
//          for(int ii=1;ii<=2*n+1;ii++)cout<<ld[ii]<<" ";
//          cout<<endl;
        }
    }
}

by chenjliang @ 2023-07-18 18:40:46

#include <bits/stdc++.h>
using namespace std;
long long a[1000001], b[100001], ld[1000001];

long long xds(int l, int r, int now) {
    if (l == r) {
        a[now] = b[l];
        return a[now];
    }
    long long mid = (l + r) / 2;
    a[now] = xds(l, mid, now * 2) + xds(mid + 1, r, now * 2 + 1);
    return a[now];
}
void push_down(int l,int r,int now){
    if(l==r){
        return;
    }
    if(ld[now]){
        a[now*2]=a[now*2]+((r+l)/2-l+1)*ld[now];
        a[now*2+1]=a[now*2+1]+(r-(r+l)/2)*ld[now];
        ld[now*2]+=ld[now];
        ld[now*2+1]+=ld[now];
        ld[now]=0;
    }
}
long long getsum(int l, int r, int sl, int sr, int now) {
    if (l >= sl && r <= sr){
        return a[now];
    }
    push_down(l,r,now);
    long long sum = 0;
    int mid = (l + r) / 2;
    if (sl <= mid)
        sum += getsum(l, mid, sl, sr, now * 2);
    if (sr > mid)
        sum += getsum(mid + 1, r, sl, sr, now * 2 + 1);
    return sum;
}

/*void in2_up(int l, int r, int now, long long num) {
    a[now] += (r-l+1)*num;
    if (now == 1)
        return;
    if (now % 2)
        in2_up(2 * l - r - 2, r, (now - 1) / 2, num);
    else
        in2_up(l, 2 * r - l, now / 2, num);
    return;
}

//mid=(l+r)/2=>l+r=2mid=>l=2mid-r=>l=2(mid+1)-r-2
void inner_up(int l, int r, int now, long long num) {
    a[now]+=num;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    inner_up(l, mid, now * 2, num), inner_up(mid + 1, r, now * 2 + 1, num);
    return;
}*/

void update(int l, int r, int sl, int sr, int now, int num) {
    if (l >= sl && r <= sr) {
        //in2_up(l, r, now, num);
        a[now]+=num*(r-l+1);
        ld[now]+=num;
        return;
    }
    push_down(l,r,now);
    int mid = (l + r) / 2;
    if (sl <= mid)
        update(l, mid, sl, sr, now * 2, num);
    if (sr > mid)
        update(mid + 1, r, sl, sr, now * 2 + 1, num);
    a[now]=a[now*2]+a[now*2+1];
    return;
}

int main() {
    int n = 0, m = 0, temp = 0, t1 = 0, t2 = 0, t3 = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    xds(1, n, 1);
    for (int i = 1; i <= m; i++) {
        cin >> temp;
        if (temp == 1) {
            cin >> t1 >> t2 >> t3;
            update(1, n, t1, t2, 1, t3);
        } else {
            cin >> t1 >> t2;
            cout << getsum(1, n, t1, t2, 1) << endl;
//          for(int ii=1;ii<=2*n+1;ii++)cout<<a[ii]<<" ";
//          cout<<endl;
//          for(int ii=1;ii<=2*n+1;ii++)cout<<ld[ii]<<" ";
//          cout<<endl;
        }
    }
}

改成这样就过了
注意数据范围要long long,id数组开小了,update()里也要push_down(),在update()回溯时再算一次就可以完成父亲节点的更新,不需要in2_up(),push_down()里儿子节点的标记要累加父亲的,不能直接赋值

by Eltaos_xingyu @ 2023-07-19 08:50:28

已AC，谢谢大佬