We have an array of integer a[1], a[2], ... , a[N] and a number M.
We take a version of selection sort like this:
for i := 1 to M do
for j := i + 1 to N do
if (a[i] > a[j]) then swap(a[i], a[j])
After the program end, count the number of swap operator in it.
Limitation:
1 <= M <= N <= 105
abs(ai) <= 109
Example:
Input:
4 2
3 2 -1 -4
Output:
5
Explain:
After first loop of j: -4 3 2 -1
After second loop of j: -4 -1 3 2
So the number of swap operator is 5.
We can solve this problem by divide-and-conquer.
First, we consider solving the region of [1, n]. For solving this region, we can divide it into two regions, [1, n / 2] and [n / 2 + 1, n].
For each region, we just recursively run the "solve" function to count how many (i, j) pairs that satisfy i < j and Ai > Aj.
What I've said is, we suppose that the solve function can give us the right answer of the region [l, r].
What we should actually do is merge two regions after solving them.
Due to the function is correct, we could just do not consider the (i, j) pairs inside the region, but between two regions that we should merge.
Okay, let us consider how to merge the regions. We suppose after merging, the big region is sorted. We could do this by merge sort.
While doing merge sort, we just have to calculate the (i, j) pairs between the two regions. So we can use two integers indicating the position that we have scanned. For example, we have two regions: 1 3 5 7 and 2 4 6 8. Then, if the first pointer is pointed to 5, we should just consider how many numbers are smaller than five in the second region. So we move the pointer in the second region to 4. So we can solve this problem in just O(n) time complexity.
We just have to do this: solve(l, r) m = (l + r) >> 1 solve(l, m) solve(m + 1, r) merge_and_calculate(l, m, m + 1, r)
So we can get the answer in
Unable to parse markup [type=CF_TEX]
complexity.Why? We could easily know that T(n) = 2 × T(n / 2) + O(n). Through some mathematical analysis, we could get
Unable to parse markup [type=CF_TEX]
This is my code, hope it'll help:
UPD. Sorry about misreading the problem.
You forgot about number M, which limits number of iterations.
Sorry about misunderstanding it.
How come after the second loop of j, the array becomes -1 -4 3 2 ? According to the pseudocode, shouldn't it become -4 -1 3 2 ?
Thank you, it is my mistake. It is fixed now.
During contest, no one solved this problem. It is hard.
I've randomly came across this blog. What contest was this problem part of? I know that there are high chances that you don't remember it, but the problem is really interesting.
Dunno why but Korean OJ has it https://www.acmicpc.net/problem/11027
did anyone figured out the solution ?
Does this idea work for the problem? (Maybe I did some mistake in the code) :
My code is wrong and the problem is that after the i-th step when we want to rebuild the minimum-stack, some new elements between i and index.back() will be added. We can handle this by answering this queries :
And it can be done using segment tree.