LIS of Pairs#10821
You have pairs (a_1, b_1), (a_2, b_2), \dots, (a_n, b_n) of integers, where 1 \leq a_i, b_i \leq m holds for all .
Let's define f(i, j) as the length of the longest strictly increasing subsequence of the sequence \{a_i, b_i, a_j, b_j\}.
It's clear that 1 \leq f(i, j) \leq 4.
For every from to , find the number of ordered pairs with 1 \le i, j \le n, for which f(i, j) = k.
Note that a sequence labeled with \{i_1, i_2, \dots, i_k\} is an increasing subsequence of \{a_1, a_2, \dots, a_n\} only if:
1 \leq i_1 < i_2 < \dots < i_k \leq n
a_{i_1} < a_{i_2} < \dots < a_{i_k}
The first line of the input contains integers (1 \leq n \leq 10^5, 1 \leq m \leq 10^3).
The -th of the following lines contains integers a_i, b_i (1 \leq a_i, b_i \leq m).
Print integers. The -th of them should be equal to the number of ordered pairs with 1 \le i, j \le n, for which f(i, j) = k.
Example 1
Example 2
In the first sample:
f(1, 1) = LIS(1, 2, 1, 2) = 2.
f(1, 2) = LIS(1, 2, 3, 4) = 4.
f(2, 1) = LIS(3, 4, 1, 2) = 2.
f(2, 2) = LIS(3, 4, 3, 4) = 2.
In the second sample, all numbers are equal, so we wouldn't be able to choose any increasing subsequence of length at least .