Scalar Question (2)

help
22

how you are shifting L and R according to the vector ???

23
  1. Binary search with lower_bound for L(will return index greater then L having 1)
  2. Binary search with lower_bound for R and if prev R is not equal to new R(iterator- - )
1 Like
24

it can be easily solved in O(n) for preprocessing and O(1)
for queries
basically there are 3 steps;
coutarray -count no of zeroes till i index
leftarray-store index of latest 1 on left side
right array-store index of latest 1 on right side
now for queries L R
we need to check right[L]<=R&&LEFT[R]>=L
THEB RETURN COUNTARRAY[left[r]]-COUNTARRY[right[l]]
OTHERWISE -1