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

Dynamic Segment Trees
Автор noobinho, история, 6 лет назад, По-английски

I'm trying to solve the problem: http://acm.timus.ru/problem.aspx?space=1&num=1439. It consists basically in m (1 <= m <= 10^5) queries in an ordered set which can be of two types: 1) eliminate an element of the ordered set (the number of elements eliminated is at most 10^4); 2) find the kth element of the ordered set. The ordered set can have at most n elements (1 <= n <= 10^9).The elements are {1,2,...,n} at the beginning. I tryed to code a dynamic segment tree to solve in O(m*logn) of time, as follows:https://ideone.com/e.js/jLFIMv. However, it gave MLE. So, I want to know what I can do to improve the memory used. Thanks in advance

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

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

Why do you indent your code so weirdly?

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

At the current time your node is 32 bytes size. You can use indexes in array / vector against pointers because one pointer is 8 bytes, but one index is 4 bytes (32-8=24, 66% memory). You exactly need to keep integers l and r in node? Maybe you can put l and r as parameters in functions in "set" and "get" queries?

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

    With the contraints that were given (1 <= n <= 10^9) I think it's infeasible to use indexes in array. I think the only way is doing the segment tree with pointers and dynamically. It would be possible to use a segment tree in an array if it was possible to do a compression in the elements of the ordered sets (an offline solution), but I can't realize how to do that.

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

      I mean that we have a vector, that contains nodes. Root has index 0. When we add child, we do push back in end and save value (int)tree.size()-1 as index of child.

      UPD: Accepted with 52 MB memory

      UPD 2: Accepted with 26 MB memory

      As you can see, optimizations of using memory, which I said, works

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

        Wow, thank you! It was really helpful

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

          It was helpful for me too, because I did not know about Dynamic Segment Tree before, can you provide a list on problems which can be easy solved with this structure, maybe on coseforces?

          And your solutions works in O(mlog(n)) time

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

            I didn't know this structure before this problem. In fact, I'm doing a list that my teacher gave me and there is only this problem about dynamic segment trees there, but there is a post from three years ago in codeforces with another problems: https://codeforces.me/blog/entry/19080

            Yes, I realized that my solution works in O(m*logn). I think it would work in O(m*logn²) if I used updateSegTree(query(num,Root,1,n),-1,Root); but as I did q = query(num,Root,1,n); and after updateSegTree(q,-1,Root,1,n); it works in O(m*logn). Is it correct?

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

              On each set or get query you add new log(n) vertices, so it is O(m * log(n)), thanks for link

              → Ответить