frank1369blogger's blog

Help with a problem
By frank1369blogger, history, 6 years ago, In English

https://www.spoj.com/problems/DQUERY/

can anybody give me a fenwick tree approach for this problem?

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

Sort all queries by j, create an array L initially consisting of N zeros, then for each ind = 0...N-1 set L[ind] = 1 and L[pos] = 0, where pos is the previous occurrence of a[ind] in a, now you can answer on all queries [i, ind] by finding sum of L[i...ind].

→ Reply