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

Timus 1439
Автор MarioYC, 13 лет назад, По-английски
I tried to solve this problem using Binary Index Tree and Binary Search, also I used coordinate compression, keeping the positions in which I made a delete operation. Then I do Binary Search over the function

(x - (number of deleted which are less or equal than x))

the problem is that when I've deleted a number twice the function won't be motonous, hence the Binary Search fails.

Is there other way to solve it with BIT?
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

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

there is no need to delete a number twice since number of the door to delete is given for the current moment, so if you store in your BIT only real numbers of deleted doors, there will never be a collision

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    but, how can I calculate real numbers for deleted doors before I start using the BIT?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      you can solve this problem online, just find the real number (like you are answering a 'L' query) before inserting a new node
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        when you say "inserting a new node" you mean I should use some Binary Search Tree?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          oh, certainly I meant binary tree that can fast calculate number of nodes with keys in some interval like cartesian tree. but our coach said that he got accepted just supporting a sorted array of deleted rooms.

          PS: before your post I thought that BIT is the same as BST... thank you for noting about that structure! it seems to be interesting
          → Ответить