思考题so late?

Dazzit Again

This is an easy version of OBCYSIO 28)
You are given an integer sequence A of length N and another sequence B of length M. Then imagine a game:
First, you choose exactly M different elements and arrange them, let's call this C. And the enemy will random shuffle B. You all break iff for each 1\leq i\leq M,C_i\geq B_i.
If you choose optimally, what's the best all break probability you will get?

Example

A={1,2,3,4,5}
B={2,3,5}
Answer= 0.33333333333333
Explain
When you choose 3 4 5:
{3,4,5} vs {2,3,5} all break
{3,4,5} vs {2,5,3} NOT all break because 4<5 {3,4,5} vs {3,2,5} all break {3,4,5} vs {3,5,2} NOT all break {3,4,5} vs {5,3,2} NOT all break {3,4,5} vs {5,2,3} NOT all break So the answer is 1/3.

Constriants

1\leq M\leq N\leq 10^5,0\leq A_i,B_i\leq 10^9

Solution

It's easy to see that we always choose the maximum M elements from A. Then the problem can be seen as:"How many permutation of B that we will get an all break?"
Let's sort the array C from big to small, then we consider each element in C to be a "slot". An element from B can be placed into a slot if only C_i\geq B_i, and this must be an interval 1~xxx.
We sort the intervals by endpoint. Let's represent sorted invervals as the array X. Then the answer is \prod_{i=1}^m(X_i-i+1)
For example, if the array C={5,4,3} and B={2,3,5} then X={3,3,1}, after sorted {1,3,3}.
So the answer is (1-1+1)\times (3-2+1)\times (3-3+1)=2