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

Query solving in most optimised way
Автор gXa, история, 6 лет назад, По-английски

Initially the array contain all 1s.

There are two type of operation:

1 A: update arr[A] = 0.

2 A: Find index of Ath 1 in the array.

Number of elements, 1<=N<=(1e6)

Number of queries, 1<=Q<=(1e6)

I tried tree statistic. However, it didn't pass.

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

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

build a segment tree wich in each node you save the number of 1's in [l, r)

update is simple.

and for answering a query in the query function check if A is smaller or equal to the number of 1's in the left node then go left in the segment tree,

otherwise go to the right child and decrease A with the number of 1's in the left child; o(nlogn)

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

Can you provide a link for that problem?

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

Answer queries in the reverse order

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

Can be done in O(logN) per query using a BIT.

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

    how is it O(logN) ? , considering you are doing binary search on bit .isn't it O(log^2N)

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

      You can binary search on the bit itself. Check topcoder tutorial for BIT.

      → Ответить