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
BIT can be used for finding prefix maximum. So, we can use two BITs to find this maximum.
If we remove the absolute function, we get two conditions h[j] <= h[i] - d or h[j] >= h[i] + d.
- For first condition, we can directly use BIT on compressed values in ascending order
- For second condition, we can use BIT on compressed values in descending order.
Now both the queries are in the form of prefix query.
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.
A single BIT can be used for general range max/min queries, see my submission below.
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:
- 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.
- Prefix (or Suffix) Minimums, under the condition that the updates are only decreases
Can you do anything more general than this?