frank1369blogger's blog

Help with a problem
By frank1369blogger, history, 4 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?
»
4 years ago, # |
← 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain more? I don't get your approach.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      What exactly? L[i] = 1 means that i is the last occurrence of a[i] in the current prefix.

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

        thanks a lot! I finally got it.

        → Reply