线段树70pts求调

P3372 【模板】线段树 1

zty8426 @ 2023-07-21 11:26:36

不知道为什么只有70pts

#include<bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define re register
using namespace std;
const int N = 1e5 + 5;
int n,m;
ll a[N],tot = 1;
ll tree[N << 2],lazy[N << 2];
//int ls[N << 2],rs[N << 2];
inline int getsum(re int p,re int l,re int r,re int lx,re int rx)
{
    if(l >= lx && rx >= r) return tree[p];
    re int mid = l + r >> 1;
    if(lazy[p] != 0)
    {
        if(l != mid) lazy[ls] += lazy[p];
        if(r != mid) lazy[rs] += lazy[p];
        tree[ls] += lazy[p] * (mid - l + 1);
        tree[rs] += lazy[p] * (r - mid);
        lazy[p] = 0;
    }
    if(lx <= mid && rx > mid) return getsum(ls,l,mid,lx,mid) + getsum(rs,mid + 1,r,mid + 1,rx);
    if(rx <= mid) return getsum(ls,l,mid,lx,rx);
    if(lx > mid) return getsum(rs,mid + 1,r,lx,rx);
}
inline void updata(re int p,re int l,re int r,re int lx,re int rx,re ll sum)
{
    if(l >= lx && rx >= r)
    {
        tree[p] += sum * (r - l + 1);
        lazy[p] += sum;
        return;
    }
    re int mid = l + r >> 1;
    if(lazy[p] != 0)
    {
        if(l != mid) lazy[ls] += lazy[p];
        if(r != mid) lazy[rs] += lazy[p];
        tree[ls] += lazy[p] * (mid - l + 1);
        tree[rs] += lazy[p] * (r - mid);
        lazy[p] = 0;
    }
    if(lx <= mid && rx > mid) updata(ls,l,mid,lx,mid,sum),updata(rs,mid + 1,r,mid + 1,rx,sum);
    if(rx <= mid) updata(ls,l,mid,lx,rx,sum);
    if(lx > mid) updata(rs,mid + 1,r,lx,rx,sum);
    tree[p] = tree[ls] + tree[rs];
}
inline void build(re int p,re int l,re int r)
{
    if(l == r) {tree[p] = a[l];return;}
    re int mid = l + r >> 1;
    build(ls,l,mid),build(rs,mid + 1,r);
    tree[p] = tree[ls] + tree[rs];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(re int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    build(1,1,n);
    for(re int i = 1,l,r,pos;i <= m;++i)
    {
        scanf("%d",&pos);
        if(pos == 1)
        {
            ll k;
            scanf("%d%d%lld",&l,&r,&k);
            updata(1,1,n,l,r,k);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",getsum(1,1,n,l,r));
        }
    }
    return 0;
}

by GoldenFishX @ 2023-07-21 11:29:49

你getsum是int的返回值..


by zty8426 @ 2023-07-21 11:31:39

@Big_Caibi 就是这个问题,谢谢


|