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 A_i > A_j.

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]

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:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define gi gI()

using namespace std;

typedef long long ll;

inline ll gI() {
    ll p = 0, flag = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    while ('0' <= c && c <= '9') p = p * 10 + (c - '0'), c = getchar();
    return p * flag;
}

int const MAXN = 100001;

int n, A[MAXN];
int L[MAXN], R[MAXN];
int ans = 0;

void merge(int l1, int r1, int l2, int r2) {
    //printf("Call Stack(%d, %d, %d, %d)\n", l1, r1, l2, r2);
    memcpy(L + 1, A + l1, sizeof(int) * (r1 - l1));
    memcpy(R + 1, A + l2, sizeof(int) * (r2 - l2));
    int i = l1, j = l2, pos;
    while (i < r1) {
	while (A[i] > A[j] && j < r2) ++ j;
	ans += j - l2;
	++ i;
    }
    i = 1, j = 1, pos = l1;
    while (i <= r1 - l1 && j <= r2 - l2) {
	if (i == r1 - l1 + 1) A[pos++] = R[j++];
	else if (j == r2 - l2 + 1) A[pos++] = L[i++];
	else {
	    if (L[i] < R[j]) A[pos++] = L[i++];
	    else A[pos++] = R[j++];
	}
    }
    //rep(i, l1, r2) printf("A[%d] = %d\n", i, A[i]);
}

void solve(int l, int r) {
    if (l + 1 >= r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid, r);
    merge(l, mid, mid, r);
}

int main() {
    n = gi;
    rep(i, 1, n) A[i] = gi;
    solve(1, n + 1);
    cout << ans << endl;
    //rep(i, 1, n) printf("A[%d] = %d\n", i, A[i]);
    return 0;
}

UPD. Sorry about misreading the problem.

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 ?

During contest, no one solved this problem. It is hard.

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 :

• What's the rightmost element greater than X in [L,R].

And it can be done using segment tree.

#include <bits/stdc++.h>
using namespace std;
#define N (101*1000)

int n,m,a[N],ans;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	deque <int> index,value;
	for(int i=n;i>=1;i--)
	{
		while(value.size() && a[i]<=value.back())value.pop_back(),index.pop_back();
		index.push_back(i);
		value.push_back(a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		if(index.back()==i)a[i]=value.back();
		while(value.size() && a[i]<=value.back())value.pop_back(),index.pop_back();
		ans+=value.size();
		value.push_back(a[i]);
		value.pop_front();
	}
	cout<<ans<<"\n";
	return 0;
}