Codeforces Round 271 Problem E Pillars

general
1

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

2

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
3

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
4

A single BIT can be used for general range max/min queries, see my submission below.

5

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?