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 Estrella_Explore @ 2024-11-28 17:26:40
@unsigned_char
给个样例
by unsigned_char @ 2024-11-28 17:31:15
@Estrella_Explore
输入：
3 8
2 1
1 1 3 2
1 1 2 4
1 2 3 3
1 1 3 1
2 1
2 2
2 3输出：
0
3
3
3by Estrella_Explore @ 2024-11-28 17:40:21
@unsigned_char
……？
哥们你 main 呢
by Estrella_Explore @ 2024-11-28 17:46:25
@Estrella_Explore
如果是 方伯伯的OJ 那道题，我就按蒟蒻的理解帮您补全代码了（
~好像蒟蒻并不会写这题（但是查个 RE 还是很轻松的~
by unsigned_char @ 2024-11-28 17:47:27
@Estrella_Explore 实际上我发的是代码片段
int main()
{
freopen("odt.in", "r", stdin);
freopen("odt.out", "w", stdout);
int n, q;
cin >> n >> q;
if (n > 100)
solve1(n, q);
else
solve(n, q);
return 0;
}by unsigned_char @ 2024-11-28 17:48:06
@Estrella_Explore \bx
by Estrella_Explore @ 2024-11-28 17:48:45
@unsigned_char
或者您给个题号也行（我没有在您的提交记录里找到类似的题）
by Estrella_Explore @ 2024-11-28 17:50:41
@unsigned_char
OKOK
运行日志如下：
❯ fkccf ./b.cpp
./b.cpp: In member function ‘int maxSegTree::modify(int, int, int, int, int)’:
./b.cpp:26:31: 警告：conversion from ‘std::__cxx1998::vector<maxSegTree::Node, std::allocator<maxSegTree::Node> >::size_type’ {aka ‘long unsigned int’} to ‘int’ may change value [-Wconversion]
26 | now = pool.size() - 1;
| ~~~~~~~~~~~~^~~
./b.cpp: In function ‘void solve(int, int)’:
./b.cpp:66:16: 警告：unused parameter ‘n’ [-Wunused-parameter]
66 | void solve(int n, int q) {
| ~~~~^
[Info]: Compilation of ./b.cpp succeeded.
[Info]: Executable file: ./b.out
[Info]: Test case ./b.in detected.
------> Use this test case as stdin? [Y/n]
[Info]: Using ./b.in as the test case.
=================================================================
==54216==ERROR: AddressSanitizer: heap-use-after-free on address 0x5100000000f8 at pc 0x60a6e9983148 bp 0x7ffc7ad68350 sp 0x7ffc7ad68340
WRITE of size 4 at 0x5100000000f8 thread T0
#0 0x60a6e9983147 in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#1 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#2 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#3 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#4 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#5 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#6 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#7 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#8 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#9 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#10 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#11 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#12 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#13 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#14 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#15 0x60a6e9982e2f in maxSegTree::modify(int, int, int, int, int) b.cpp:34
#16 0x60a6e9983424 in maxSegTree::modify(int, int) b.cpp:56
#17 0x60a6e997cd19 in solve(int, int) b.cpp:76
#18 0x60a6e997d643 in main b.cpp:96
#19 0x7d5443634e07 (/usr/lib/libc.so.6+0x25e07) (BuildId: 98b3d8e0b8c534c769cb871c438b4f8f3a8e4bf3)
#20 0x7d5443634ecb in __libc_start_main (/usr/lib/libc.so.6+0x25ecb) (BuildId: 98b3d8e0b8c534c769cb871c438b4f8f3a8e4bf3)
#21 0x60a6e997c2c4 in _start (/home/explore/luogu/b.out+0x102c4) (BuildId: 62029e6895dda59bb8b64b5202da268b63a2bf36)
0x5100000000f8 is located 184 bytes inside of 192-byte region [0x510000000040,0x510000000100)
freed by thread T0 here:
#0 0x7d54444ff652 in operator delete(void*, unsigned long) /usr/src/debug/gcc/gcc/libsanitizer/asan/asan_new_delete.cpp:164
#1 0x60a6e9980d43 in std::__new_allocator<maxSegTree::Node>::deallocate(maxSegTree::Node*, unsigned long) /usr/include/c++/14.2.1/bits/new_allocator.h:172
#2 0x60a6e9980d43 in std::allocator_traits<std::allocator<maxSegTree::Node> >::deallocate(std::allocator<maxSegTree::Node>&, maxSegTree::Node*, unsigned long) /usr/include/c++/14.2.1/bits/alloc_traits.h:513
#3 0x60a6e9980d43 in std::__cxx1998::vector<maxSegTree::Node, std::allocator<maxSegTree::Node> >::_M_realloc_append<maxSegTree::Node>(maxSegTree::Node&&)::_Guard::~_Guard() /usr/include/c++/14.2.1/bits/vector.tcc:616
previously allocated by thread T0 here:
#0 0x7d54444fe4f2 in operator new(unsigned long) /usr/src/debug/gcc/gcc/libsanitizer/asan/asan_new_delete.cpp:95
#1 0x60a6e99819bb in std::__new_allocator<maxSegTree::Node>::allocate(unsigned long, void const*) /usr/include/c++/14.2.1/bits/new_allocator.h:151
SUMMARY: AddressSanitizer: heap-use-after-free b.cpp:34 in maxSegTree::modify(int, int, int, int, int)
Shadow bytes around the buggy address:
0x50fffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x50fffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x50ffffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x50ffffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x510000000000: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
=>0x510000000080: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd[fd]
0x510000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x510000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x510000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x510000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x510000000300: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==54216==ABORTING
[Info]: Output is shown below and saved as ./b.ans.
0
[Hint]: You can use "diff ./b.ans <Standard Answer>" to compare with the expected output.
by unsigned_char @ 2024-11-28 17:51:35
@Estrella_Explore 是我们校内 OJ 的题，不过我调试发现 RE 的原因在线段树树内（即 class maxSegTree）
by Estrella_Explore @ 2024-11-28 17:55:35
@unsigned_char
您不用急，这个报错只有一点点有用的信息，就是程序在释放了一个内存块之后，仍然尝试访问它
我在根据报错的那个地址定位具体代码