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

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

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
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +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)

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

Can you provide a link for that problem?

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

Answer queries in the reverse order

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

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

→ Ответить