咋回事，一直调不好

hh__hh @ 2023-10-06 21:35:17

#include<bits/stdc++.h>
#define lc cur << 1
#define rc lc | 1
#define int long long
using namespace std;

const int N = 1e5 + 20;
int w[N];
struct edge {
    int l,r,sum,add;
} a[N];

void build(int cur,int l,int r)
{
    a[cur].l = l;
    a[cur].r = r;
    if (l == r) {
        a[cur].sum = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(lc,l,mid);
    build(rc,mid + 1,r);
    a[cur].sum = a[lc].sum + a[rc].sum;
}
void pushdown(int cur)
{
    a[lc].sum += (a[lc].r - a[lc].l + 1) * a[cur].add;
    a[lc].add += a[cur].add;
    a[rc].sum += (a[rc].r - a[rc].l + 1) * a[cur].add;
    a[rc].add += a[cur].add;
    a[cur].add = 0;
}
void updata(int cur,int x,int y,int k)
{
    if (a[cur].l <= x && a[cur].r <= y) {
        a[cur].add += k;
        a[cur].sum += (a[cur].r - a[cur].l + 1) * k;
        return;
    }
    if (a[cur].add) pushdown(cur);
    int mid = a[cur].l + a[cur].r >> 1;
    if (x <= mid) updata(lc,x,y,k);
    if (y > mid) updata(rc,x,y,k);
    a[cur].sum = a[lc].sum + a[rc].sum;
}
int query(int cur,int x,int y)
{
    if (x <= a[cur].l && a[cur].r <= y) return a[cur].sum;
    if (a[cur].add) pushdown(cur);
    int sum = 0;
    int mid = a[cur].l + a[cur].r >> 1;
    if (x <= mid) sum += query(lc,x,y);
    if (y > mid) sum += query(rc,x,y);
    return sum;
}
signed main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[N];
    build(1,1,n);

    int op,x,y,k;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y  >> k;
            updata(1,x,y,k);
        }
        else {
            cin >> x >> y;
            cout << query(1,x,y) << endl;
        }
    }

    return 0;
}

by Blue_Flower @ 2023-10-06 21:41:49

首先，线段树的数组要开到 N*4 的大小

by hh__hh @ 2023-10-06 22:06:08

还是一样

输入样例

它输出

11
8
36

by Linge_Zzzz @ 2023-10-06 22:11:06

大体看了一下

1. 数组应该是 N * 4 大小
2. update函数第一行，a[cur].l <= x 写反了，应改为 x <= a[cur].l

by Linge_Zzzz @ 2023-10-06 22:11:32

@hh__hh

by NO_OI_NO_LIFE @ 2023-10-06 22:12:03

@hh__hh update

if (a[cur].l <= x/*x <= a[cur].l*/ && a[cur].r <= y) {

不过还有毛病,等一下

by 聊机 @ 2023-10-06 22:12:49

@hh__hh

 if (a[cur].l <= x && a[cur].r <= y) {

这句错了，没往后看。

by NO_OI_NO_LIFE @ 2023-10-06 22:13:41

@hh__hh 彻底改好了,关注别忘了

#include<bits/stdc++.h>
#define lc cur << 1
#define rc lc | 1
#define int long long
using namespace std;

const int N = 1e5 + 20;
int w[N];
struct edge {
    int l,r,sum,add;
} a[N << 2];//

void build(int cur,int l,int r)
{
    a[cur].l = l;
    a[cur].r = r;
    if (l == r) {
        a[cur].sum = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(lc,l,mid);
    build(rc,mid + 1,r);
    a[cur].sum = a[lc].sum + a[rc].sum;
}
void pushdown(int cur)
{
    a[lc].sum += (a[lc].r - a[lc].l + 1) * a[cur].add;
    a[lc].add += a[cur].add;
    a[rc].sum += (a[rc].r - a[rc].l + 1) * a[cur].add;
    a[rc].add += a[cur].add;
    a[cur].add = 0;
}
void updata(int cur,int x,int y,int k)
{
    if (a[cur].l >= x && a[cur].r <= y) {//
        a[cur].add += k;
        a[cur].sum += (a[cur].r - a[cur].l + 1) * k;
        return;
    }
    if (a[cur].add) pushdown(cur);
    int mid = a[cur].l + a[cur].r >> 1;
    if (x <= mid) updata(lc,x,y,k);
    if (y > mid) updata(rc,x,y,k);
    a[cur].sum = a[lc].sum + a[rc].sum;
}
int query(int cur,int x,int y)
{
    if (x <= a[cur].l && a[cur].r <= y) return a[cur].sum;
    if (a[cur].add) pushdown(cur);
    int sum = 0;
    int mid = a[cur].l + a[cur].r >> 1;
    if (x <= mid) sum += query(lc,x,y);
    if (y > mid) sum += query(rc,x,y);
    return sum;
}
signed main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];//
    build(1,1,n);

    int op,x,y,k;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y  >> k;
            updata(1,x,y,k);
        }
        else {
            cin >> x >> y;
            cout << query(1,x,y) << endl;
        }
    }

    return 0;
}

by 聊机 @ 2023-10-06 22:14:36

cin>>w[N]真逆天（

by NO_OI_NO_LIFE @ 2023-10-06 22:15:04

看来我才是第一个改成AC哒!

by hh__hh @ 2023-10-06 22:15:45

@2022zhangyuanhao 已关注

感谢