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

Help with a problem
Автор frank1369blogger, история, 4 года назад, По-английски

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

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

Thanks.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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].

→ Ответить