UPD on 03/03/2026
Hi,
On Library Checker's "Segment Add Get Min", my offline Li Chao Tree implementation runs about 2x faster than the second fastest submission (as of 15/02/2026).
Key optimizations
- Radix sort for discretization
- Bottom-up, segment-tree-based structure
- Reduced unnecessary computations
Results
Library Checker 64 ms vs 128 ms → 2x faster
QOJ 57 ms vs 157 ms → ~2.75x faster
Benchmarks were measured on the latest official test data under -std=c++23 -O2.
I won’t go into details here, but the full code is available in the repository. (There are also other very fast implementations in the repo.)
If anyone has comparable benchmarks or alternative optimizations, I’d be happy to discuss.
Thanks.
GGs on beating my 128ms!
Another potential optimization I see is to track $$$cnt_v =$$$ how many $$$get\_min()$$$ queries are left to visit vertex $$$v$$$:
When doing $$$get\_min()$$$ we subtract 1 from every vertex on the path.
When doing $$$line\_add()$$$ we break immediately if $$$cnt_v = 0$$$.
But looks like it makes solution substantially slower, at least on the given data: https://judge.yosupo.jp/submission/353102
Thanks. On the given test data, the overhead (cache missing, I guess?) seems to dominate the pruning benefit, so it actually slows things down (as your submission shows). Still an interesting idea though — might behave differently under other distributions. I'll try it later.
What a big hand!