两份代码有哪处不同?

P3372 【模板】线段树 1

xlpri @ 2024-11-15 21:27:38

两份代码,一份之前写的,一份RE,没检查出漏了哪句

之前的:

#include <bits/stdc++.h>

using namespace std;

int n,m,k,num[100007];
struct node
{
    long long num;
    long long laz;
}tre[400028];

void pushup(int u)
{
    tre[u].num = tre[u*2].num + tre[u*2 + 1].num;
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        tre[u].num = num[l];
        return;
    }
    int mid = (l + r)/2;
    build(u*2,l,mid);
    build(u*2 + 1,mid + 1,r);
    pushup(u);
}

bool ifin(int L,int R,int l,int r)    /*l,r查询区间,L,R树区间*/
{
    return (l <= L) && (R <= r);
}

bool ifout(int L,int R,int l,int r)
{
    return (L > r) || (R < l);
}

void maketag(int u,int len,long long x)
{
    tre[u].laz += x;
    tre[u].num += len*x;
    return;
}

void pushdown(int u,int l,int r)
{
    int mid = (l + r)/2;
    maketag(u*2,mid - l + 1,tre[u].laz);
    maketag(u*2 + 1,r - mid,tre[u].laz);
    tre[u].laz = 0;
}

long long query(int u,int L,int R,int l,int r)
{
    if(ifin(L,R,l,r))
    {
        return tre[u].num;
    }
    else if(!ifout(L,R,l,r))
    {
        int mid = (L + R)/2;
        pushdown(u,L,R);
        return query(u*2,L,mid,l,r) + query(u*2 + 1,mid + 1,R,l,r);
    }
    else return 0;
}

void update(int u,int L,int R,int l,int r,long long x)
{
    if(ifin(L,R,l,r))
    {
        maketag(u,R - L + 1,x);
    }
    else if(!ifout(L,R,l,r))
    {
        int mid = (L + R)/2;
        pushdown(u,L,R);
        update(u*2,L,mid,l,r,x);
        update(u*2 + 1,mid + 1,R,l,r,x);
        pushup(u);
    }
    else return;
}

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> num[i];
    build(1,1,n);
    while(m--)
    {
        int t,x,y;
        cin >> t >> x >> y;
        if(t == 1)
        {
            cin >> k;
            update(1,1,n,x,y,k);
        }
        else cout << query(1,1,n,x,y) << endl;
    }
    return 0;
}

RE:

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

ll n,m,x,y,num[100007];
struct Tree
{
    ll num;
    ll laz;
} tre[400028];

void pushnum(int u)
{
    tre[u].num = tre[u*2].num + tre[u*2+1].num;
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        tre[u].num = num[l];
        return;
    }
    int mid = (l + r)/2;
    build(u*2, l, mid);
    build(u*2+1, mid+1, r);
    pushnum(u);
}

bool ifin(int L,int R,int l,int r)  //L,R大区间  r,l查找区间
{
    return (l <= L && R <= r);
}

bool ifout(int L,int R,int l,int r)
{
    return (R < l || r < L);
}

void maketag(int u,int l,int r,ll x)
{
    tre[u].laz += x;
    tre[u].num += (r - l + 1)*x;
    return;
}

void update_laz(int u,int l,int r)
{
    int mid = (l + r)/2;
    maketag(u*2, l, mid, tre[u].laz);
    maketag(u*2+1, mid+1, r, tre[u].laz);
    tre[u].laz = 0;
}

ll ffind(int u,int L,int R,int l,int r)
{
    if(ifin(L,R,l,r))
    {
        return tre[u].num;
    }
    else if(!ifout(L,R,l,r))
    {
        int mid = (l + r)/2;
        update_laz(u,L,R);
        return ffind(u*2, L, mid, l, r) + ffind(u*2+1, mid+1, R, l, r);
    }
    else return 0;
}

void update(int u,int L,int R,int l,int r,ll x)
{
    if(ifin(L,R,l,r))
    {
        maketag(u,l,r,x);
    }
    else if(!ifout(L,R,l,r))
    {
        int mid = (l + r)/2;
        update_laz(u,L,R);
        update(u*2, L, mid, l, r, x);
        update(u*2+1, mid+1, R, l, r, x);
        pushnum(u);
    }
    return;
}

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> num[i];
    build(1,1,n);
    while(m--)
    {
        int t;
        cin >> t >> x >> y;
        if(t == 1)
        {
            int k;
            cin >> k;
            update(1,1,n,x,y,k);
        }
        else cout << ffind(1,1,n,x,y) << endl;
    }
    return 0;
}

by qazsedcrfvgyhnujijn @ 2024-11-15 21:31:32

RE 的那份修改和查询函数里面的 mid 都写错了;
你可能需要一个文件对比工具。


by IRIDESCENTqwq @ 2024-11-15 21:48:20

@xlpri query和update中的mid写错了,把小写l打成大写L了……(我的习惯是在线段树结构体中加两个变量l和r,代表当前区间的左右界,这样就不会和参数l、r搞混了)


by xlpri @ 2024-11-15 21:52:24

@qazsedcrfvgyhnujijn@IRIDESCENTqwq

感谢,已AC


by qazsedcrfvgyhnujijn @ 2024-11-15 21:57:06

@xlpri 补充:我的习惯是把当前节点的 [l, r]lr 表示,正操作/询问的区间用 queryl -> qlqueryr -> qr 表示,然后直接在线段树最前面 #define mid ((l + r) >> 1)


|