### gXa's blog

By gXa, history, 12 months ago, ,

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
•

 » 12 months ago, # |   0 Create a binary index tree, type 1 operation is trivial, type 2 operation is just query in the index J such that the prefix sum until J is equal to A, this can be done with binary search.
 » 12 months ago, # |   +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)
 » 12 months ago, # |   +1 Can you provide a link for that problem?
 » 12 months ago, # |   0 Answer queries in the reverse order
 » 12 months ago, # | ← Rev. 2 →   +5 Can be done in O(logN) per query using a BIT.
•  » » 12 months ago, # ^ |   0 how is it O(logN) ? , considering you are doing binary search on bit .isn't it O(log^2N)
•  » » » 12 months ago, # ^ |   0 You can binary search on the bit itself. Check topcoder tutorial for BIT.
 » 12 months ago, # |   0 Could you give us input and output examples?