gXa's blog

Query solving in most optimised way
By gXa, history, 7 years 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

Comments Comments (6)
| Write comment?
»
7 years 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)

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can you provide a link for that problem?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Answer queries in the reverse order

→ Reply
»
7 years 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.

→ Reply
  • »
    »
    7 years 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)

    → Reply
    • »
      »
      »
      7 years 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.

      → Reply