hi , anyone have any idea about how to solve D. Serega and Fun using treap ?

thanks for any help

I found this interesting problem here
the problem :
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 <= 10^5
abs(ai) <= 10^9
any idea for the solution please ?
thanks in advance ^_^

here is the problem
it's really an interesting problem but just a few people have solved it
I came up with o(n^2 * log2(n)) solution (using dp and segment tree)
it could pass only 40% of test cases
someone told me it could be solved using convex hull trick
so please explain your solution
thanks in advance

I have already finished wcipeg's tutorial for convex hull trick.
I tried to solve APIO'10 Commando but I'm getting WA after test 9 and the same for Usaco ACQUIRE
I tried to submit the official solutions which is posted in wcipeg tutorial but still getting WA after test 9
anyone has solved them, or there are some mistakes in their test cases ?

another question , in that tutorial all the example problems were offline version or when each new line inserted has a lower slope than any line currently in the envelope
so please give me some problem required convex hull which has no guarantee of either condition holding (each new line to be added may have any slope whatsoever)
thanks in advance
UPD : I've got AC in both Commando and ACQUIRE

for i = 1 to n 
    ans+=pow(x,i)

can it calculated in less than o(n) ? thanks in advance

I don't see any ads on Codeforces , so how does Codeforces make money ?