https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
--- Comment #13 from Raihat Zaman Neloy <raihatneloy1992 at gmail dot com> ---
(In reply to Xi Ruoyao from comment #12)
> Created attachment 47615 [details]
> patch optimizing pb_ds tree split, RFC
>
> I made up a patch but I doubt if this is really useful in competitive
> programming. (I just tried to find a problem to test the split
> functionality but I couldn't find one.)
>
> (1) Even with this patch, splitting with rb_tree_tag is still stupidly slow.
> pb_ds documentation says it is "poly-logarithmic complexity". It's too
> loose - maybe $O(log n)^3$? So the only useful case is with splay_tree_tag.
>
> (2) It's impossible to implement any "batch updating" with pb_ds. For
> example, considering a problem where we would maintain an integer set $S$,
> supporting several operations on it:
>
> add a: $S \leftarrow \{x \in S | x + a\}$
> query b: output $\min_{x \in S} |b - x|$
> rm c: remove $c$ from $S$, if $c \in S$
> ins d: insert $d$ into $S$
>
> This is a splay problem, but requiring batch updating and lazy evaluation.
> Unfortunately we just can't do it with pb_ds. I believe this "defect"
> directly makes split/join useless.
>
> Then should we add more functionality into pb_ds? I think Jonathan won't
> agree since he is absolutely correct that GCC is not to help people in
> programming contests. But if we not, pb_ds won't be very useful. Only very
> naive splay problems can be solved with it. In real contests my friend
> wang9897 can manually code a splay tree before I finish up all the
> tree_order_statistics_node_update stuff, for those naive problems.
Hi Xi,
Thanks a lot for your comment.
(1) It's true that rb_tree_tag is slower. I used splay_tree_tag to solve few
problems.
(2) It's also true that for batch-update / range-update / lazy propagation,
pb_ds not gonna work. But if the split/join works as intended, then it would
possible to get help of pb_ds where we need some kinds of 2D data-structures.
Like - a Segtree where each node may need to contain another BIT/BST for some
simple calculations.
It's also true that, as a versatile BST, I will code Treap/Splay. But for some
simple calculations like I describe, writing the whole code is also too much
costly (where we atleast have the feature, but not efficient).
On the other hand, today I tried to solve SPOJ-CITY2 with pb_ds to check if
split or join works perfectly or not, I figured out a work-around for that
(using what I got AC as well). Here is the code:
https://paste.ubuntu.com/p/w3hWpRmJSP/
I just tried to override Standard namespace's distance function to work with
that.
I also agree that GNU's purpose isn't helping people doing competitive
programming but my opinion is something like, as the feature already exists, it
can be efficient as well (which is the intended behaviour I would say) :)
