unsigned_char @ 2024-11-28 17:25:15
以下代码使用 GCC -std=c++14
选项编译会导致 RE (本机 Segment Fault,OJ Aborted),而使用 -std=c++17
或者更高标准则不会出现问题;使用 Clang++ 无论是否开启 -std=c++14
都不会出现问题
这究竟是我代码的问题还是编译器/标准库的问题?
代码如下,大致思路是实现动态开点权值线段树,包括单点修改和区间查询操作
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e9;
const int MAXN = 101; // 55pts
class maxSegTree
{
struct Node
{
int val;
int ls, rs;
Node() : val(0), ls(-1), rs(-1) {};
};
vector<Node> pool;
int head;
void push_up(int now)
{
pool[now].val = 0;
if (pool[now].ls != -1)
pool[now].val = max(pool[now].val, pool[pool[now].ls].val);
if (pool[now].rs != -1)
pool[now].val = max(pool[now].val, pool[pool[now].rs].val);
}
int modify(int idx, int val, int s, int t, int now)
{
if (now == -1)
{
pool.push_back(Node());
now = pool.size() - 1;
}
if (s == t)
{
pool[now].val = val;
return now;
}
int mid = (s + t) / 2;
if (idx <= mid)
pool[now].ls = modify(idx, val, s, mid, pool[now].ls);
else
pool[now].rs = modify(idx, val, mid + 1, t, pool[now].rs);
push_up(now);
return now;
}
int query(int l, int r, int s, int t, int now)
{
if (now == -1)
return 0;
if (s >= l && t <= r)
return pool[now].val;
int mid = (s + t) / 2;
int ans = 0;
if (l <= mid)
ans = max(ans, query(l, r, s, mid, pool[now].ls));
if (r > mid)
ans = max(ans, query(l, r, mid + 1, t, pool[now].rs));
return ans;
}
public:
// void modify(int idx, int val) { head = modify(idx, val, 1, N, head); }
void modify(int idx, int val) { head = modify(idx, val, 1, N, head); }
int query(int l, int r) { return query(l, r, 1, N, head); }
maxSegTree() : head(-1) {}
};
maxSegTree f[MAXN][2];
// f[0]: b[i] > b[i - 1], f[1]: b[i] < b[i - 1]
// f[1] <- f[0]: query max[v + 1, N] + 1
// f[0] <- f[1]: query max[1, v - 1] + 1
void solve(int n, int q)
{
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int l, r, x;
cin >> l >> r >> x;
for (int i = l; i <= r; ++i)
{
const int v1 = f[i][0].query(x + 1, N);
const int v2 = f[i][1].query(1, x - 1);
f[i][1].modify(x, v1 + 1);
f[i][0].modify(x, v2 + 1);
}
}
if (op == 2)
{
int t;
cin >> t;
cout << max(f[t][0].query(1, N), f[t][1].query(1, N)) << "\n";
}
}
}
by unsigned_char @ 2024-11-28 19:10:52
@Estrella_Explore 拜谢大佬
鉴定为:GCC 标准库出锅
by Estrella_Explore @ 2024-11-28 19:15:04
@unsigned_char
我是菜逼
其次,关于 stdlibc++,他死?了
(发怒
by Estrella_Explore @ 2024-11-28 19:24:28
@unsigned_char
控制变量法:
md 不是标准库的锅,只能怪 g++
libstdc++ 是 g++ 使用的 cpp 实现,
clang 切换过去没问题;
而强制使 g++ 使用 libc++,即 clang 使用的 cpp 实现,出锅了,只能怪 g++
我*****
❯ clang++ --std=c++14 -stdlib=libc++ ./b.cpp -o ./b.out
❯ ./b.out
0
3
3
3
❯ clang++ --std=c++14 -stdlib=libstdc++ ./b.cpp -o ./b.out
❯ ./b.out
0
3
3
3
❯ g++ -std=c++14 ./b.cpp -o ./b.out -nostdinc++ -I/usr/include/c++/v1 -L/usr/lib -lc++ -lc++abi
❯ ./b.out
0
[1] 63643 segmentation fault (core dumped) ./b.out
by Estrella_Explore @ 2024-11-28 19:28:08
(订正一下,经过我的测试,clang 默认用的还是 libstdc++,但是可以通过 -stdlib=libc++
指定)
by unsigned_char @ 2024-11-28 19:40:48
@Estrella_Explore \bx 是我调查的少了
by Estrella_Explore @ 2024-11-28 19:42:42
@unsigned_char
您的那个代码我调 AC 了,是gnu实现的问题,强行对于 vector
预先分配空间就行
构造函数改成 maxSegTree() : head(-1) { pool.reserve(MAX_SIZE); }
就能过了
(我设的 const int MAX_SIZE = 1e3+50
,对于这个样例足够了)
by Estrella_Explore @ 2024-11-28 19:45:33
玄学问题给我调虚脱了(((
就刚刚大概从 七点十几 开始,越调越兴奋,越调越上头,~血压也越高~
终于 AC 了我去,但是我还是想说 GNU 死码了(
by unsigned_char @ 2024-11-28 20:04:29
@Estrella_Explore 感觉还是很奇怪,如果是 STL 的锅的话,为什么 clang 使用 libstdc++ 却没有问题
算了,先这样吧
by Estrella_Explore @ 2024-11-28 20:13:37
@unsigned_char
算了,我累了,反正你收获了 AC 不是吗(