Canyou pls tell me hint regarding coverthemall question in fenwick trees

#1

i am unable to think of a logic using bit

#2

THhink about cordinate compression and then building answer by inserting small elements in bit

#3

lets say we are considering a pair (x,y) of soldiers who communicate
assume x<y, so |x-y| = (y-x)
now we have 2 cases.
Case 1: b >= c
in this case the answer will simply be (y-x)*b, so total cost for this case is
sigma (y(i) - x) *b
simplifying further, we get sigma (y) b - x b (number of soldiers having less bombs than current soldier)
To answer this one, we require 2 things:

  1. number of soldiers lying ahead having less bombs
  2. sum of their positions
    this can be answered with segment tree / fenwick tree.

Case 2: b < c
total cost for this case is
sigma [(y(i) - x) * c(i)]
simplifying:
sigma [y(i) c(i)] - sigma [x c(i)]
= sigma [y(i) c(i)] - x (sigma c(i) )
the first term can be found out by precomputing all y(i)*c(i) values, and proceeding in a similar way

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.