一个奇怪我的问题

P3372 【模板】线段树 1

illidan_ @ 2024-05-18 20:19:49

一个正常的线段树，队友看了也没什么问题，但是在洛谷上提交开了o2就会T，不开o2就rte了，c++的编译器试了很多都是这个问题，但是测试点一在我自己的编译器上是正确的，今天换了自动识别语言的编译器关掉o2就过了，大佬们能帮忙看一下吗，我做了一道其他的线段树也是这个问题```cpp

include <bits/stdc++.h>

define int long long

define ull unsigned long long

define id(i,j) (i-1)*m+j

define endl '\n'

using namespace std;

const int N = 2e5+10; typedef pair<int,int> PII;

int n,m,ans,T; int a[N], tree[N<<2], tag[N<<2];

int push_up(int p) { tree[p] = tree[p 2] + tree[p 2 + 1]; }

int add_tag(int id, int l, int r, int num) { tag[id] += num; tree[id] += (r - l + 1) * num; }

int push_down(int id, int l, int r) { if(tag[id] != 0) { int mid = (l + r) >> 1; add_tag(id 2, l, mid, tag[id]); add_tag(id 2 + 1, mid + 1, r, tag[id]); tag[id] = 0; } }

void update(int L, int R, int l, int r, int id, int num) { if(l >= L && r <= R) { add_tag(id,l,r,num); return ; } push_down(id, l, r); int mid = (l + r) >> 1; if(mid >= L) update(L,R,l,mid,id2,num); if(mid < R) update(L,R,mid + 1,r,id 2 + 1,num); // 等于号 push_up(id); }

int query(int L, int R, int l, int r, int id) { if(l >= L && r <= R) { return tree[id]; } push_down(id,l,r); int res = 0, mid = (l + r) / 2; if(mid >= L) res += query(L,R,l,mid,id2); if(mid < R) res += query(L,R,mid + 1,r,id 2 + 1); return res; }

void build(int l, int r, int id) { if(l == r) { tree[id] = a[l]; return; } int mid = (l + r) / 2; build(l, mid, id 2); build(mid + 1, r, id 2 + 1); push_up(id); }

signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n>>T; for(int i = 1 ;i <= n; i ++) cin>>a[i];
build(1,n,1);
while(T --) { int op,L,R,num; cin>>op; if(op == 1) { cin>>L>>R>>num; update(L,R,1,n,1,num); } else { cin>>L>>R; cout<<query(L,R,1,n,1)<<endl; } } return 0; }

by illidan_ @ 2024-05-18 20:20:12

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define id(i,j) (i-1)*m+j
#define endl '\n'

using namespace std;

const int N = 2e5+10;
typedef pair<int,int> PII;

int n,m,ans,T;
int a[N], tree[N<<2], tag[N<<2];

int push_up(int p)
{
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
}

int add_tag(int id, int l, int r, int num)
{
    tag[id] += num;
    tree[id] += (r - l + 1) * num;
}

int push_down(int id, int l, int r)
{
    if(tag[id] != 0)
    {
        int mid = (l + r) >> 1;
        add_tag(id * 2, l, mid, tag[id]);
        add_tag(id * 2 + 1, mid + 1, r, tag[id]);
        tag[id] = 0;
    }
}

void update(int L, int R, int l, int r, int id, int num)
{
    if(l >= L && r <= R)
    {
        add_tag(id,l,r,num);
        return ;
    }
    push_down(id, l, r);
    int mid = (l + r) >> 1;
    if(mid >= L) update(L,R,l,mid,id*2,num);
    if(mid < R) update(L,R,mid + 1,r,id * 2 + 1,num); // 等于号
    push_up(id);
}

int query(int L, int R, int l, int r, int id)
{
    if(l >= L && r <= R) 
    {
        return tree[id];
    }
    push_down(id,l,r);
    int res = 0, mid = (l + r) / 2;
    if(mid >= L) res += query(L,R,l,mid,id*2);
    if(mid < R) res += query(L,R,mid + 1,r,id * 2 + 1);
    return res;
}

void build(int l, int r, int id)
{
    if(l == r) 
    {
        tree[id] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid + 1, r, id * 2 + 1);
    push_up(id);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>T;
    for(int i = 1 ;i <= n; i ++) cin>>a[i];  
    build(1,n,1);     
    while(T --)
    {
        int op,L,R,num;
        cin>>op;
        if(op == 1) 
        {
            cin>>L>>R>>num;
            update(L,R,1,n,1,num);
        }
        else 
        {
            cin>>L>>R;
            cout<<query(L,R,1,n,1)<<endl;
        }
    }
    return 0;
}

by illidan_ @ 2024-05-18 20:20:46

不好意思，代码放错了

by _wsq_ @ 2024-05-18 20:31:52

push_up，add_tag 和 push_down 三个返回值非 void 的函数没有 return 导致的。

by _wsq_ @ 2024-05-18 20:35:32

这是未定义行为，开 O2 会被优化掉导致寄掉，不开 O2 时 C++ 和 GCC 不同版本会导致情况不同。

by HAha20120522 @ 2024-05-18 20:36:03

你在本地上应该是warning

by _wsq_ @ 2024-05-18 20:39:35

你仔细看就会发现，自动识别的语言是 C++14 (GCC 9)，你自己选的是 C++17 和 C++20 （GCC 版本为 13.2.0），C++ 和 GCC 版本都不同。

by _wsq_ @ 2024-05-18 20:41:23

改成这样

void push_up(int p)
{
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
}

void add_tag(int id, int l, int r, int num)
{
    tag[id] += num;
    tree[id] += (r - l + 1) * num;
}

void push_down(int id, int l, int r)
{
    if(tag[id] != 0)
    {
        int mid = (l + r) >> 1;
        add_tag(id * 2, l, mid, tag[id]);
        add_tag(id * 2 + 1, mid + 1, r, tag[id]);
        tag[id] = 0;
    }
}

或者这样

int push_up(int p)
{
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
    return 0;
}

int add_tag(int id, int l, int r, int num)
{
    tag[id] += num;
    tree[id] += (r - l + 1) * num;
    return 114514;
}

int push_down(int id, int l, int r)
{
    if(tag[id] != 0)
    {
        int mid = (l + r) >> 1;
        add_tag(id * 2, l, mid, tag[id]);
        add_tag(id * 2 + 1, mid + 1, r, tag[id]);
        tag[id] = 0;
    }
    return 1919810;
}

by illidan_ @ 2024-05-27 19:58:53

@54Tiger 十分感谢

|