不懂就问

P3372 【模板】线段树 1

liuchenyu2022 @ 2023-03-04 16:03:07

这份代码

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
    long long x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m;
struct node{
    int le,ri;
    unsigned long long sum;
    unsigned long long zy;
}tree[4*1000001];
unsigned long long d[1000001];
void push_up(int p)
{
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
} 
void build(int rt,int le,int ri)//构建线段树 
{
    tree[rt].le=le;
    tree[rt].ri=ri;
    tree[rt].zy=0;
    if(le==ri)
    {
        tree[rt].sum=d[le];
        return ;
    }
    int mid=(le+ri)>>1;
    build(rt<<1,le,mid);
    build((rt<<1)+1,mid+1,ri);
    push_up(rt); 
    return ;
}
void lazy(int rt,unsigned long long k)
{
    tree[rt].zy+=k;
    tree[rt].sum += k*(tree[rt].ri-tree[rt].le+1);
}
void push_down(int rt)
{
    lazy(rt<<1,tree[rt].zy);
    lazy(rt<<1|1,tree[rt].zy);
    tree[rt].zy=0;
}
void update(int rt,int nl,int nr,unsigned long long k)//单点修改 
{
    if(nl<=tree[rt].le&&nr>=tree[rt].ri)
    {
        lazy(rt,k);
        return ;
    }
    push_down(rt);
    unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
    if(nl<=mid)
        update(rt<<1,nl,nr,k);
    if(nr>mid)
        update((rt<<1)+1,nl,nr,k);
    push_up(rt);
    return ;
}
unsigned long long query1(int rt,int le,int ri)//查询[le...ri]的和 
{
    // 如果 
    if(le<=tree[rt].le&&tree[rt].ri<=ri)
        return tree[rt].sum;
    push_down(rt);
    unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
    unsigned long long Sum=0;
    if(le<=mid)
        Sum+=query1(rt<<1,le,ri);
    if(ri>mid)
        Sum+=query1((rt<<1)+1,le,ri);
    return Sum;
}
long long query2(int rt,int le,int ri)//查询[le...ri]的和 
{
    if(tree[rt].le==le&&tree[rt].ri==ri)
        return tree[rt].sum;
    push_down(rt);
    long long mid=(tree[rt].le+tree[le].ri)/2;
    if(ri<=mid)
        return query2(rt<<1,le,ri);
    else if(le>mid)
        return query2((rt<<1)+1,le,ri);
    else
        return query2(rt<<1,le,mid)+query2((rt>>1)+1,mid+1,ri);
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        d[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int tmp=read();
        if(tmp==1){
            int le =read();
            int ri= read();
//          int val =read();            
            update(1,le,ri,read());
        }
        else
        {
            int le =read();
            int ri= read();
//          cout<<query1(1,le,ri)<<"\n";
            printf("%lld\n",query1(1,le,ri)); 
        }
    }
    return 0;
}

是对的\ \ 这份代码

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;
inline unsigned long long read()
{
    long long x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m;
struct node{
    int le,ri;
    unsigned long long sum;
    unsigned long long zy;
}tree[4*1000001];
unsigned long long d[1000001];
void push_up(int p)
{
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
} 
void build(int rt,int le,int ri)//构建线段树 
{
    tree[rt].le=le;
    tree[rt].ri=ri;
    tree[rt].zy=0;
    if(le==ri)
    {
        tree[rt].sum=d[le];
        return ;
    }
    int mid=(le+ri)>>1;
    build(rt<<1,le,mid);
    build((rt<<1)+1,mid+1,ri);
    push_up(rt); 
    return ;
}
void lazy(int rt,unsigned long long k)
{
    tree[rt].zy+=k;
    tree[rt].sum += k*(tree[rt].ri-tree[rt].le+1);
}
void push_down(int rt)
{
    lazy(rt<<1,tree[rt].zy);
    lazy(rt<<1|1,tree[rt].zy);
    tree[rt].zy=0;
}
void update(int rt,int nl,int nr,unsigned long long k)//单点修改 
{
    if(nl<=tree[rt].le&&nr>=tree[rt].ri)
    {
        lazy(rt,k);
        return ;
    }
    push_down(rt);
    unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
    if(nl<=mid)
        update(rt<<1,nl,nr,k);
    if(nr>mid)
        update((rt<<1)+1,nl,nr,k);
    push_up(rt);
    return ;
}
unsigned long long query1(int rt,int le,int ri)//查询[le...ri]的和 
{
    // 如果
    if(le<=tree[rt].le&&tree[rt].ri<=ri)
        return tree[rt].sum;
    push_down(rt);
    unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
    unsigned long long Sum=0;
    if(le<=mid)
        Sum+=query1(rt<<1,le,ri);
    if(ri>mid)
        Sum+=query1((rt<<1)+1,le,ri);
    return Sum;
}
long long query2(int rt,int le,int ri)//查询[le...ri]的和 
{
    if(tree[rt].le==le&&tree[rt].ri==ri)
        return tree[rt].sum;
    push_down(rt);
    long long mid=(tree[rt].le+tree[le].ri)/2;
    if(ri<=mid)
        return query2(rt<<1,le,ri);
    else if(le>mid)
        return query2((rt<<1)+1,le,ri);
    else
        return query2(rt<<1,le,mid)+query2((rt>>1)+1,mid+1,ri);
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        d[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int tmp=read();
        if(tmp==1){
            update(1,read(),read(),read());
        }   
        else
        {
            int le =read();
            int ri= read();
//          cout<<query1(1,le,ri)<<"\n";
            printf("%lld\n",query1(1,le,ri)); 
        }   
    }
    return 0;
}

是错的


by liuchenyu2022 @ 2023-03-04 16:15:38

咋回事啊?


by pjykk @ 2023-03-04 16:18:00

update(1,read(),read(),read());

不要这么写。是UB。


by liuchenyu2022 @ 2023-07-04 14:26:26

谢谢


|