How can we solve the problem using BIT ? After figuring out the basic dp we need a data structure to find best[i]=max(best[j])+1 with j<i,h[j]h[i]>= D. We can find this using segment tree. Can we find this maximum using BIT ? Link to the problem http://codeforces.com/contest/474/problem/E asked 07 Oct '14, 12:51

Yes, it is possible: see for example this : http://codeforces.com/contest/474/submission/8133621 BIT can be made to work for range max/min queries, with point updates. answered 07 Oct '14, 23:21
I've read the problem, but haven't read your code properly. I'm worried by your generalization... As I see it, BIT can't be used for general Range Minimum Queries. It works for this problem because you only want prefix/suffix maximums, and more importantly, the updates are only increases. ie, using BIT, you can find: 1. Prefix (or Suffix) Maximums, under the condition that the updates are only increases. ie. any update to A[i] can only increase it's value. 2. Prefix (or Suffix) Minimums, under the condition that the updates are only decreases Can you do anything more general than this?
(08 Oct '14, 22:45)
