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

Splay Tree Problem — Can it be solved using Order Statistic Tree?
Автор -synx-, история, 7 лет назад, По-английски

http://www.spoj.com/problems/ADALIST/
The problem asks to efficiently perform insert/erase/index at kth position!
I know it can be solved using Splay Tree easily in O(nlg(n)).
My question however is can we use Order Statistic Tree (PBDS) to solve it too? (inserting might cause issues, I think)

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I think it is not possible, because the elements in pbds::tree must be sorted.

But I get accepted by using ext/rope. https://www.sgi.com/tech/stl/Rope.html

(it is really slow.)

I did not find any way to use pbds' internal functions.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ask for index = build splay tree on values

ask for kth = build splay tree on positions

therefore it's not possible to do it in

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    No, this is a well-known problem that can be done with splay/rbtree/avl in O(n log n).

    (Friend, have you heard of sized balanced tree? This is famous in Chinese OI community. http://wcipeg.com/wiki/Size_Balanced_Tree)

    You need a balanced binary search tree, and maintain the size of subtree rooted at each node. Then you can binary search the k-th element of the whole tree.

    node *find_kth_node(node *n, int k) {
     int lsize = n->left ? n->left->size : 0;
     if (k < lsize) return find_kth_node(n->left, k);
     else if (k == lsize) return n;
     else return find_kth_node(n->right, k - 1 - lsize);
}

    (maintain the size is a very tedious work, because of the insertion, deletion, rotation, etc)

    Fortunately, ext/pb_ds have sized splay/rbtree implementation. But it does not have an interface to insert a node at a specified position (insert(position, value) or insert_before(iterator, value)).

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      it's finding the kth node right?

      i am not quite understand that, i mean, how could u find the kth node's(according to the value) index and insert some node in the kth position(according to the original order) in ?

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You misunderstood the problem.

        Search and insertion are both according to the index / position, not value.

        Position of k-th smallest value is not well-defined anyway, because there can be repeated values, right?

        → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

Can I solve it through STL Vector? I didn't know the Splay tree or what you guys are telling... Can you guys suggest me some good blog upon this topic? I am stuck at this problem getting 17 TLE using vector.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you want I can publish a blog on 32nd March on how to solve it using vectors.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      I hope You can do so. But I am extremely sure that I can be as equal as you in next 29th February**** and See you then guy.

      → Ответить