List: Another Problem about Beautiful PairsRestricted Sorting

Another Problem about Beautiful Pairs

This problem is so difficult. We use Square Root Decomposition. To prevent the two loops, we divide the problem into two parts. If we just count by this equal, when is small, the time is O(n), and the complete time is going to be . So we set . Case 1: We just count the coordinate that satisfy the $$a_i \ge B$$. And at most we can check $$\frac{n}{\sqrt{n}} = \sqrt{n}$$ times. Case 2: and Here we know that the case and there exits and , so we have . So we just count preview B position.

And totally is . We don't need to consider other cases, you can prove this. And note that when the case 1 we also should check the answer before . The code is became easy.

Restricted Sorting

Firstly i want to solve this by graph because this is totally can be viewed as a lian tong problem. We just consider that if there exits two element can't be touched, what should we do. Let's consider the limit. We get touched by the two max number and minimum number because this always point the longest distance. So after sorting a get b, we have the condition: .