Very nice use of BIT in this problem
@nehra_1997
Thanks
1 Like
I think u use similar approach as used in inversion count using bit…
please dry run the code , hopefully u will get it …!!! If still not ,then surely I will help .
I haven’t used line sweep. Its convex hull trick. Basically we can consider lines of the form y=a[j]\cdot x + a[i] such that i<j and a[i] < a[j]. Then we can find max(a[i] + a[j] * a[k]) in O(log(n)) using convex hull trick.
Something worth stressing: for each j, there is only one line. If y=a[j] x+a[i_1] and y=a[j] x+a[i_2] are 2 valid lines for a given j, then we’ll take the one with tha larger a[i] .
can someone confirm whether my approach is correct?