RE求助

P3372 【模板】线段树 1

zhengpie @ 2024-05-07 14:35:24

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[114514];
struct segment_tree
{
    int sum,add,l,r;
}tree[114514 * 4];
void pushup(int x)
{
    tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum;
}
void addtag(int x,int v)
{
    tree[x].add += v;
    tree[x].sum += v * (tree[x].r - tree[x].l + 1);
}
void pushdown(int x)
{
    if(!tree[x].add) return;
    addtag(x * 2,tree[x].add);
    addtag(x * 2 + 1,tree[x].add);
    tree[x].add = 0;
}
void build(int x,int pl,int pr)
{
    if(pl == pr)
    {
        tree[x].l = pl;
        tree[x].r = pr;
        tree[x].sum = a[pl];
        return;
    }
    int mid = (pl + pr) / 2;
    build(x * 2,pl,mid);
    build(x * 2 + 1,mid + 1,pr);
    pushup(x);
}
int query(int x,int pl,int pr)
{
    if(pl <= tree[x].l && tree[x].r <= pr) return tree[x].sum;
    pushdown(x);
    int res = 0,mid = (pl + pr) / 2;
    if(pl <= mid) res += query(x * 2,pl,pr);
    if(pr > mid) res += query(x * 2 + 1,pl,pr);
    return res;
}
void change(int x,int pl,int pr,int v)
{
    if(pl <= tree[x].l && tree[x].r <= pr) 
    {
        addtag(x,v);
        return;
    }
    int mid = (pl + pr) / 2;
    if(pl <= mid) change(x * 2,pl,pr,v);
    if(pr > mid) change(x * 2 + 1,pl,pr,v);
    pushup(x);
}
signed main()
{
    //ios::sync_with_stdio(0);
    scanf("%lld %lld",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int bbj = 1,op,x,yyr1345y,k;bbj <= m;bbj++)
    {
        scanf("%lld",&op);
        if(op == 1)
        {
            scanf("%lld %lld %lld",&x,&yyr1345y,&k);
            change(1,x,yyr1345y,k);
        }
        if(op == 2)
        {
            scanf("%lld %lld",&x,&yyr1345y);
            printf("%lld\n",query(1,x,yyr1345y));
        }
    }

    return 0;
}

by Leonid @ 2024-05-07 15:06:35

@zhengpie

void build(int x,int pl,int pr)
{
    tree[x].l = pl;
    tree[x].r = pr;
    if(pl == pr)
    {
        tree[x].sum = a[pl];
        return;
    }
    int mid = (pl + pr) / 2;
    build(x * 2,pl,mid);
    build(x * 2 + 1,mid + 1,pr);
    pushup(x);
}

by OneSheeep @ 2024-05-07 15:08:19

@zhengpie

还有上面提到了的 $build$ 内的问题。 改正过的代码: ```cpp #include<bits/stdc++.h> using namespace std; #define int long long int n,m,a[114514]; struct segment_tree { int sum,add,l,r; }tree[114514 * 4]; void pushup(int x) { tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum; } void addtag(int x,int v) { tree[x].add += v; tree[x].sum += v * (tree[x].r - tree[x].l + 1); } void pushdown(int x) { if(!tree[x].add) return; addtag(x * 2,tree[x].add); addtag(x * 2 + 1,tree[x].add); tree[x].add = 0; } void build(int x,int pl,int pr) { tree[x].l = pl; tree[x].r = pr; if(pl == pr) { tree[x].sum = a[pl]; return; } int mid = (pl + pr) / 2; build(x * 2,pl,mid); build(x * 2 + 1,mid + 1,pr); pushup(x); } int query(int x,int pl,int pr) { if(pl <= tree[x].l && tree[x].r <= pr) return tree[x].sum; pushdown(x); int res = 0,mid = (tree[x].l + tree[x].r) / 2; //here if(pl <= mid) res += query(x * 2,pl,pr); if(pr > mid) res += query(x * 2 + 1,pl,pr); return res; } void change(int x,int pl,int pr,int v) { if(pl <= tree[x].l && tree[x].r <= pr) { addtag(x,v); return; } int mid = (tree[x].l + tree[x].r) / 2;// here if(pl <= mid) change(x * 2,pl,pr,v); if(pr > mid) change(x * 2 + 1,pl,pr,v); pushup(x); } signed main() { //ios::sync_with_stdio(0); scanf("%lld %lld",&n,&m); for(int i = 1;i <= n;i++) scanf("%lld",&a[i]); build(1,1,n); for(int bbj = 1,op,x,yyr1345y,k;bbj <= m;bbj++) { scanf("%lld",&op); if(op == 1) { scanf("%lld %lld %lld",&x,&yyr1345y,&k); change(1,x,yyr1345y,k); } if(op == 2) { scanf("%lld %lld",&x,&yyr1345y); printf("%lld\n",query(1,x,yyr1345y)); } } return 0; } ```

by zhengpie @ 2024-05-07 22:16:25

@OneSheeep 谢谢(说实话,还有一处错误,change里面没有pushdown)


|