da.2396's blog

Fenwick Tree application
By da.2396, history, 8 years ago, In English

Hi guys ,I was just lingering through problem set where I found this question http://mirror.codeforces.com/contest/368/problem/B

I was curious about whether this Question can be done using fenwick tree.(Which,apparently,I could not think of as in how to implement!? )

If u guys can implement fenwick tree for the question I would be more than overwhelmed . Or even if You can actively suggest some idea on how to proceed in implementing fenwick tree for finding distinct integers !!

Thanking you

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

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It is possible that it can be solved with Fenwick tree. You only need to do the "suffix" sum of an array bi formed by 1's if no other element in ai + 1, ai + 2, ...an equals ai, and 0 otherwise. For easy implementation as a Fenwick tree, you should reverse the problem, and find the number of different elements in some prefix of the reversed array. However, I think that a Fenwick tree is definitely an overkill, as the problem can be solved efficiently with std::set or even, given the constraints, with a boolean array counting the elements that have already appeared.

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

    Yep it would be overkilling the problem but still downvoting -4 .

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

      (Sorry for that, I upvoted) I think that codeforces users are a little mean sometimes. It is risky to post sincere (although some users may consider them trivial) questions without receiving downvotes. Thanks to codeforces I know why Facebook doesn't have an unlike button jaja

      → Reply