线段树过不了样例求调

P3372 【模板】线段树 1

DengDuck @ 2022-11-08 21:49:03

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],op,x,y,k,sum[1000005],la[400005];
void build(long long pos,long long l,long long r)
{
    if(l==r)
    {

        sum[pos]=a[l];
        //cout<<pos<<' '<<l<<' '<<r<<' '<<sum[pos]<<endl;
        return;
    }
    long long mid=(l+r)/2;
    build(pos*2,l,mid);
    build(pos*2+1,mid+1,r); 

    sum[pos]=sum[pos*2]+sum[pos*2+1];
   // cout<<pos<<' '<<l<<' '<<r<<' '<<sum[pos]<<endl;
}
void down(long long pos,long long l,long long r)
{
    la[pos*2]+=la[pos];
    la[pos*2+1]+=la[pos];
    la[pos]=0;
    long long mid=(l+r)/2;
    sum[pos*2]+=la[pos*2]*(mid-l+1);
    sum[pos*2+1]+=la[pos*2+1]*(r-mid);
    sum[pos]=sum[pos*2]+sum[pos*2+1];
}
void add(long long pos,long long l,long long r,long long el,long long er,long long k)
{
    if(r<el||er<l)return;
    if(el<=l&&r<=er)
    {
        sum[pos]+=k*(r-l+1);
        la[pos]+=k;
        return;
    }
    down(pos,l,r);
    long long mid=(l+r)/2;
    add(pos*2,l,mid,el,er,k);
    add(pos*2+1,mid+1,r,el,er,k); 
    sum[pos]=sum[pos*2]+sum[pos*2+1];   
}
long long query(long long pos,long long l,long long r,long long el,long long er)
{

    if(r<el||er<l)return 0;
    if(el<=l&&r<=er)
    {
     //   cout<<pos<<' '<<l<<' '<<r<<' '<<el<<' '<<er<<' '<<sum[pos]<<endl; 
        return sum[pos];
    }

    down(pos,l,r);
    long long mid=(l+r)/2;
   //cout<<pos<<l<<' '<<r<<' '<<el<<' '<<er<<' '<<query(pos*2,l,mid,el,er)+query(pos*2+1,mid+1,r,el,er)<<endl; 
    return query(pos*2,l,mid,el,er)+query(pos*2+1,mid+1,r,el,er); 

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    } 
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x>>y>>k;
            add(1,1,n,x,y,k); 
        }
        if(op==2) 
        {
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
}

by vvauted @ 2022-11-08 21:50:04

@DengDuck down 写错了,建议看看题解


by Asimplename @ 2022-11-08 21:52:09

您这么写 PushDown 应该是错的,应该是子节点都更新完了才往上更新吧(?


|