Please help me!!!

P3372 【模板】线段树 1

rome_empire @ 2022-12-01 01:37:40

求助各位大佬,为啥我只对了第一个点QAQ

#include<bits/stdc++.h>

#define ls (x*2)
#define rs (x*2+1)
using namespace std;
long long sumn[400005],a[400005],tag[400005];
void update(int x)
{
    sumn[x]=sumn[x*2]+sumn[x*2+1];
}

void build(int l,int r,int x)
{
    if(l==r)
    {
        sumn[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    update(x);
}

void down(int l,int r,int x) 
{

    int mid=(l+r)>>1;
    if(tag[x]>0)                  
    {
        tag[ls]=tag[rs]=tag[x];
        sumn[ls]+=(mid-l+1)*tag[x];
        sumn[rs]+=(r-mid-1+1)*tag[x];
        tag[x]=0;               
    }
}

long long query(int A,int B,int l,int r,int x)
{
    if(A<=l && r<=B)
    {
        return sumn[x];
    }
    down(l,r,x);

    int mid=(l+r)>>1;
    long long ans=0;              
    if(A<=mid)
    {
        ans=ans+query(A,B,l,mid,x*2); 
    }
    if(mid<B)
    {
        ans=ans+query(A,B,mid+1,r,x*2+1);
    }
    return ans;
} 

void change(int A,int B,int v,int l,int r,int x)
{
    if(A<=l && r<=B)
    {
        tag[x]=v;
        sumn[x]+=v*(r-l+1);
        return; 
    }
    down(l,r,x);   

    int mid=(l+r)>>1;
    if(A<=mid) change(A,B,v,l,mid,ls);
    if(mid<B)  change(A,B,v,mid+1,r,rs);
    update(x);         
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;
    int x,y,z;
    int c;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        cin>>c;
        if(c==1)
        {
            cin>>x>>y>>z;
            change(x,y,z,1,n,1);
        } 
        if(c==2)
        {
            cin>>x>>y;
            cout<<query(x,y,1,n,1)<<endl;
        }
    }
}

by rome_empire @ 2022-12-01 01:38:15

please


by VictorChen @ 2022-12-01 03:29:10

  1. pushdown函数里这句
tag[ls] = tag[rs] = tag[x];

应改为

tag[ls] += tag[x];
tag[rs] += tag[x];

因为可能当时的子节点内已经存在lazy了;

  1. 数组开小导致后面RE了 我刚试了下 把数组开成十倍能过(虽然应该不需要这么多)

by DYYqwq @ 2022-12-01 07:36:47

@VictorChen 可能需要4倍空间吧,线段树都这样


by Xeqwq @ 2022-12-01 07:41:29

@DongYUyao 四倍开了


by DYYqwq @ 2022-12-01 07:42:09

@Xeqwq (艹,我没看题


by DYYqwq @ 2022-12-01 07:45:23

@rome_empire 我发现开到600005就行了(


by rome_empire @ 2022-12-02 00:00:13

@VictorChen 谢谢了orz

刚学线段树,积累经验ing


by rome_empire @ 2022-12-02 00:00:38

@DongYUyao 我 try try


by rome_empire @ 2022-12-02 00:01:04

@DongYUyao 这个不假


|