gXa's blog

By gXa, history, 9 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • -17
  • Vote: I do not like it  

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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)

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can you provide a link for that problem?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Answer queries in the reverse order

»
9 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you give us input and output examples?