Hi, I am back to blue...
So this is regard the problem Lipshitz Sequence. I think I have solution to the problem with complexity, but it is getting TL. So I wonder, it is my complexity calculation that is wrong, or it is something with the implementation? For reference, code is here.
What I did, is first I took array of differences, for example 4 1 2 -> 3 1. Then, problem is basically asking for sum of minimum of all subarrays. Then, query [i, j] maps to the sum of minimum of subarrays of [i-1, j-2].
I'll demonstrate this method in first example, then it may be clearer for you to understand it :) Let's take first sample and fir st query.
10 4
1 5 2 9 1 3 4 2 1 7
2 4
...
First we take the difference array: 4 3 7 8 2 1 2 1 6. Then, since i=2, j=4, we take sum of minimum of subarrays of [1, 2], which is 3 7. Now it's clear, subarrays are [3], [3, 7], [7], sum is 3+7+7=17. So it's clear that problem has been transformed.
For each number, we can count how many times it is counted. Say we are considering subarray x...y. We will consider how many times maximum is added to the sum. Say a maximum occurs, the position pt (variables same as in the code, look at f function). In the code, f(x, y) find the answer for subarray x...y. So how many subarrays that maximum at position pt is included in? Well, if we pick any index x...pt and any index pt...y, it will be included. Therefore, there are a total of (pt - x + 1) * (y - pt + 1) occurrences of element at position pt. Then, we can break the subarray into two smaller subarrays (divide and conquer method) x...pt-1 and pt+1...y and recurse on those.
The querying maximum (number and index) from i to j, inclusive can be found using a segment tree in O(log n).
So, total complexity for each query satisfies T(N) = 2T(N/2) + O(log N), solution is O(N). (If you don't believe me, look here and scroll all the way down :P)
So total complexity should be O(N log N + NQ). (Initial N log n for segment tree build). But if this is right, why it is giving the TL verdict?
Thanks,
minimario
