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.

1 Like

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.

1 Like

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?