We will do parallel binary search (if you don't know what this is, you can try finding the blog in codeforces) on the answer K. Now we have update events (value X appears on position i) and query even (what's the maximum value of sum * length of a subinterval between L, R). Both queries can be done in with segment tree. Unfortunately this way the complexity is and will pass for 58 points. But if we use the fast segment tree from Al.Cash's blog it will pass. Furthermore as all values are nonnegative we can actually replace the segment tree with dsu.

For the segment tree you will need the following in each node:

1) Available suffix length and sum.

2) Available prefix length and sum.

3) Answer and length of the whole interval.

This way we can merge the nodes in time.