照着第二篇题解改了半天还是wa

P3372 【模板】线段树 1

瀛洲仙子 @ 2024-10-09 17:02:12

0pts

#include<bits/stdc++.h>
using namespace std;
typedef long long lld;
struct var
{
    int l,r;//[l,r]
    int lc,rc;
    lld summ,tag;
    var(){l=r=lc=rc=summ=tag=0;}
};var seg[300005];int cnt;
lld arr[100005];int n,m;
int build(int l,int r)
{
    if(l==r)
    {
        seg[++cnt].summ=arr[l];
        seg[cnt].l=seg[cnt].r=l;
        return cnt;
    }
    seg[++cnt].l=l;seg[cnt].r=r;
    int mid=(l+r)>>1;int k=cnt;
    seg[cnt].lc=build(l,mid);
    seg[k].rc=build(mid+1,r);
    seg[k].summ=seg[seg[k].lc].summ+seg[seg[k].rc].summ;
    return k;
}
void down(int id)
{
    seg[seg[id].lc].tag=seg[seg[id].rc].tag=seg[id].tag;
    seg[seg[id].lc].summ+=seg[id].tag*(seg[seg[id].lc].r-seg[seg[id].lc].l+1);
    seg[seg[id].rc].summ+=seg[id].tag*(seg[seg[id].rc].r-seg[seg[id].rc].l+1);
    seg[id].tag=0;return;
}
void add(int id,int l,int r,lld k)
{
    if(seg[id].l>=l and seg[id].r<=r)
    {seg[id].tag+=k;seg[id].summ+=k*(seg[id].r-seg[id].l+1);return;}
    int mid=(seg[id].l+seg[id].r)>>1;down(id);
    if(l<=mid)add(seg[id].lc,l,mid,k);
    if(r>mid)add(seg[id].rc,mid+1,r,k);
    seg[id].summ=seg[seg[id].lc].summ+seg[seg[id].rc].summ;
}
lld query(int id,int l,int r)
{
    if(seg[id].l>=l and seg[id].r<=r)
        return seg[id].summ;
    int mid=(seg[id].l+seg[id].r)>>1;
    down(id);lld ret=0;
    if(l<=mid)
        ret+=query(seg[id].lc,l,r);
    if(r>mid)
        ret+=query(seg[id].rc,l,r);
    return ret;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>arr[i];
    build(1,n);
    int op,x,y;lld k;
    /*for(int i=1;i<=cnt;++i)
        printf("%d:[%d,%d],(%d,%d),{%d,%d}\n",i,seg[i].l,seg[i].r,seg[i].lc,
        seg[i].rc,seg[i].summ,seg[i].tag);*/
    while(m--)
    {
        int op;cin>>op;
        if(op==1)
        {
            cin>>x>>y>>k;
            add(1,x,y,k);
        }
        else
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
}

by Hagasei @ 2024-10-09 17:15:09

@瀛洲仙子

29 行改为

seg[seg[id].lc].tag+=seg[id].tag;
seg[seg[id].rc].tag+=seg[id].tag;

39,40 行改为

if(l<=mid)add(seg[id].lc,l,r,k);
if(r>mid)add(seg[id].rc,l,r,k);

by 瀛洲仙子 @ 2024-10-09 19:47:56

@Hagasei 感谢感谢 已通过 此贴完结


|