蒟蒻写的程序,求调

P3372 【模板】线段树 1

Atserckcn @ 2024-03-16 15:19:46

程序:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
ll a[MAXN];
struct NODE{
    ll l,r,sum,lz;
}node[MAXN<<2];
ll n,m,op,x,y,z;
void build(ll l,ll r,ll x)//ok
{
    if(l==r)
    {
        node[x].sum=a[r];
        return;
    }
    ll mid=(l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    node[x].sum+=node[x*2+1].sum+node[x*2].sum;
    return;
}
ll getnum(ll l,ll r,ll s,ll t,ll x)//ok
{
    if(l<=s&&r>=t)
    {
        return node[x].sum;
    }
    ll mid,sum=0;
    mid=(s+t)/2;
    if(node[x].lz!=0)
    {
        node[x*2].sum+=(mid-s+1)*node[x].lz;
        node[x*2+1].sum+=(t-mid)*node[x].lz;
        node[x*2].lz+=node[x].lz;
        node[x*2+1].lz+=node[x].lz;
    }
    node[x].lz=0;
    if(l<=mid)
    {
        sum=getnum(l,r,s,mid,x*2);
    }
    if(r>mid)
    {
        sum+=getnum(l,r,mid+1,t,x*2+1);
    } 
    return sum;
}
void update(ll l,ll r,ll c,ll s,ll t,ll p)
{
    if(l<=s&&t<=r)
    {
        node[p].sum+=(t-s+1)*c;
        node[p].lz+=c;
        return;
    }
    ll mid=(l+r)/2;
    if(node[p].lz!=0)
    {
        node[p*2].sum+=(mid-s+1)*node[p].lz;
        node[p*2+1].sum+=(t-mid)*node[p].lz;
        node[p*2].lz+=node[p].lz;
        node[p*2+1].lz+=node[p].lz;
    }
    node[p].lz=0;
    if(l<=mid)
    {
        update(l,r,c,s,mid,p*2);
    }
    if(r>mid)
    {
        update(l,r,c,mid+1,t,p*2+1);
    }
    node[p].sum=node[p*2].sum+node[p*2+1].sum;
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(ll i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            scanf("%d",&z);
            update(x,y,z,1,n,1);
        }
        else
        {
            printf("%d\n",getnum(x,y,1,n,1));
        }
    }
    return 0;
}

蒟蒻已经知道是在update函数那里死循环了,求各位大佬调QAQ


by _Spectator_ @ 2024-03-16 15:24:26

@20120110_linjiale ll mid=(l+r)/2; -> ll mid=(s+t)/2;


by Atserckcn @ 2024-03-16 15:28:56

@cjrawa https://www.luogu.com.cn/record/151113514

我改了,但是还是只有70分……QAQ


by _Spectator_ @ 2024-03-16 15:32:23

@20120110_linjiale scanf/printf 里的 %d 改成 %lld


by Atserckcn @ 2024-03-16 15:35:15

@cjrawa

https://www.luogu.com.cn/record/151115879

过了,谢谢大佬!!(已关注)


by Atserckcn @ 2024-03-16 15:35:55

@cjrawa

加团队吗?


|