I can give you lessons in implementation to avoid these mistakes later, you can take my number from eyad

RIP

I don't get it, max(a, b) = max(b, a) right ?

brutal

After 6 hours of debugging, the compiler was debugged.

Try it by writing a max function and see if it works.

Or try to change your compiler. You are using C++17 (GCC 7-32), use C++20 (GCC 13-64) might be that this will work.

Here's how to debug the code in 10 minutes

Step 1: Generate a random test case using g++ gen.cpp && ./a.out > input.txt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int N = 1e5;

mt19937 rng(69);

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  cout << t << '\n';
  int n = N, k = 3237750685;
  cout << n << ' ' << k << '\n';
  for (int i = 1; i <= n; i++) {
    cout << uniform_int_distribution<>(6, 1e9)(rng) << " \n"[i == n];
  }
}

Step 2: Compile with sanitizer and run against the test case

> g++ 1983F.cpp -O2 -fsanitize=undefined,address -g && ./a.out < input.txt
=================================================================
==109285==ERROR: AddressSanitizer: heap-use-after-free on address 0x150d908e77f8 at pc 0x56238fbb8a6b bp 0x7ffe5cba52d0 sp 0x7ffe5cba52c0
READ of size 4 at 0x150d908e77f8 thread T0
    #0 0x56238fbb8a6a in int const& std::max<int>(int const&, int const&) /usr/include/c++/14.1.1/bits/stl_algobase.h:262
    #1 0x56238fbb8a6a in Trie::get(int, int, int) /home/qmk/code/cpp/1983F.cpp:57

Step 3: Add bound checking for line 57

res = max(get(x, mid, st[node].child[0]), st[node].child[1] < st.size() ? st[st[node].child[1]].mx : 0);

Step 4: Profit 269512762

Same behavior replicated here. Switching order fixes it. Interestingly, adding optimization level O0 or O2 both give random outputs.

My best guess for why this happens is that std::max evaluates the second half of the max function, at some point stores a reference to a value in the vector of nodes, but then reallocates the vector while resizing in the recursive step, messing with that reference.

This behavior could not be replicated on Godbolt (but I didn't try very hard). I'm also not familiar enough with low-level programming to use an actual debugger, so I can't give a better answer.

UB should be more suspected in this case, since the order of evaluation of parameters should not matter.

See the comment from qmk above.