Блог пользователя Petr

Автор Petr, история, 10 месяцев назад, По-английски
  • Проголосовать: нравится
  • +137
  • Проголосовать: не нравится

»
10 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Why downvote this? Maybe you didn't see the link. Very interesting post! Enjoyed reading it!

»
10 месяцев назад, скрыть # |
 
Проголосовать: нравится +33 Проголосовать: не нравится
  • »
    »
    10 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Very nice! It does seem that this can do a lot of things we need, but the multitude of options makes me think that a simplification is possible. For example, maybe the operations that use index can be handled uniformly with operations that use key and support key lazy add? Similarly, range add/min/max can probably be unified into a single lazy operation, similar to how AtCoder's lazysegtree does it.

    So I'm looking for the simplest abstraction that allows to express all your checkboxes :)

    • »
      »
      »
      10 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! I'm not too familiar with how AtCoder's lazy segtree works, but any operation that can be done with a lazy segtree can be unified in a treap in the same way. The buttons for enabling sum/min/max and range add/set only just add code into the "value" and "lazy" structs, which is my way of writing generic segtrees.

      Currently, I do range updates and queries in a segtree-style traversal for better constant. However, I don't know a way to perform a range reverse that doesn't involve two splits followed by two merges, so I'm not sure if that can be unified without increasing the constant factor by a lot.

      I haven't considered generalising keys and indices, but for me I've found it convenient to have the distinction since sometimes I use both (e.g. querying index of some key, finding i'th smallest element). Some other stuff like treap "union" where you merge sorted sets only makes sense in terms of keys and not indices. There are also some weird treaps that might be too hard/not worth to generalise like the treap version of segment tree beats, which hopefully will never be used in a real problem.

»
10 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится -6 Проголосовать: не нравится

From the 9 contestants mentioned above, it seems that only hos.lyric has a templated splay tree, but even in her case the abstraction seems to leak the implementation details (push/pull)

Wait, is hos.lyric a girl?

Edit: She is.