https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
Xi Ruoyao <xry111 at mengyan1223 dot wang> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |xry111 at mengyan1223 dot wang
--- Comment #3 from Xi Ruoyao <xry111 at mengyan1223 dot wang> ---
(In reply to Oleksandr Kulkov from comment #0)
> In the end of the split in policy based data structures extension function
> split finish is called
> (https://code.woboq.org/gcc/libstdc++-v3/include/ext/pb_ds/detail/
> bin_search_tree_/split_join_fn_imps.hpp.html#__gnu_pbds::detail::
> PB_DS_BIN_TREE_NAME::split_finish) which works in O(n) due to call of
> std::distance of two iterators. In the official documentation it is said to
> be O(log n) though. This problem can be resolved by keeping subtree sizes in
> metadata like it is done in tree_order_statistics_node_update. Is it
> possible to fix the bug?
Hi Zlobober,
I remember you because I performed very badly in two contests prepared by you
:).
I can't see any way to fix it w/o maintenance of subtree sizes. We can do that
but then...
1. Is it worthy? But I think WE can answer "YES" because there are no guys
other than competitive programmers use it! So maybe we should ask: would
Jonathan (and libstdc++ team) accept such a "fix"?
2. If we maintain subtree sizes for all pb_ds BBSTs should we remove
tree_order_statistics_node_update, or make it a nop?
3. What if pb_ds is immediately removed after we fix it? (I remember one of my
Cilk fix, which is removed before the next release and never backported so I
just effectively wasted some time.)
4. Even if the fix is done in GCC 10, the onsite contestants have to wait for
additional several years because Ubuntu used in contest won't use latest GCC.
And for online contestants I think the better way is to copy a BBST from the
personal code library.
