LIS of Pairs#12863

LIS of Pairs (Editorial)

First, let's count the number of pairs with LIS = 4. Clearly, we should consider only pairs with a_i<b_i, and have to count the number of such pairs that b_i<a_j. For this, count the — the number of pairs with a_i < b_i\le x for each with prefix sums in O(n+m), and for each (a_i, b_i) with a_i<b_i add cnt[a_i-1] to the answer.

We count the number of pairs with LIS = 1 similarly.

Let's count the number of pairs with f(i, j)\ge 3, and then we will subtract the number of pairs with LIS = 4 from it, obtaining the number of pairs with LIS = 3. We will find the number of pairs with LIS = 2 similarly.

Now, if f(i, j)\ge 3, at least one of the following must hold:

  • a_i < b_i < max(a_j, b_j)

  • min(a_i, b_i) < a_j < b_j

It's easy to count the number of pairs , which satisfy a_i < b_i < max(a_j, b_j): again, count — the number of pairs (a_i, b_i) with a_i<b_i\le x, we can do this with prefix sums. Similarly we can find the number of pairs which satisfy min(a_i, b_i) < a_j < b_j. It remains to subtract the number of pairs which satisfy both to avoid double counting.

So, we consider only pairs with a_i<b_i, and need to count the number of pairs such that b_i < b_j and a_i < a_j. This can be done with prefix sums: count cnt[x][y]— the number of pairs with a_i\le x and b_i\le y, and add dp[a_i-1][b_i-1] for every pair.

This solution works in O(n + m^2).