НЗП пар#10821

НЗП пар

1 секунда

256 мегабайтів

Дуже складна

У вас є $n$ пар цілих чисел $(a_{1}, b_{1}), (a_{2}, b_{2}), \dots, (a_{n}, b_{n})$ (a_1, b_1), (a_2, b_2), \dots, (a_n, b_n), де $1 \leq a_{i}, b_{i} \leq m$ 1 \leq a_i, b_i \leq m для всіх $i$ .

Позначимо $f (i, j)$ f(i, j) як довжину найдовшої строго зростаючої підпослідовності послідовності ${a_{i}, b_{i}, a_{j}, b_{j}}$ \{a_i, b_i, a_j, b_j\}.

Очевидно, що $1 \leq f (i, j) \leq 4$ 1 \leq f(i, j) \leq 4.

Для кожного $k$ від $1$ до $4$ , знайдіть кількість впорядкованих пар $(i, j)$ з $1 \leq i, j \leq n$ 1 \leq i, j \leq n, для яких $f (i, j) = k$ f(i, j) = k.

Зверніть увагу, що послідовність, позначена ${i_{1}, i_{2}, \dots, i_{k}}$ \{i_1, i_2, \dots, i_k\}, є зростаючою підпослідовністю послідовності ${a_{1}, a_{2}, \dots, a_{n}}$ \{a_1, a_2, \dots, a_n\} лише тоді, коли:

$1 \leq i_{1} < i_{2} < \dots < i_{k} \leq n$ 1 \leq i_1 < i_2 < \dots < i_k \leq n
$a_{i_{1}} < a_{i_{2}} < \dots < a_{i_{k}}$ a_{i_1} < a_{i_2} < \dots < a_{i_k}

Вхідні дані

Перший рядок вхідних даних містить $2$ цілі числа $n, m$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5, $1 \leq m \leq 1 0^{3}$ 1 \leq m \leq 10^3).

Кожен $i$ -й із наступних $n$ рядків містить $2$ цілі числа $a_{i}, b_{i}$ a_i, b_i ( $1 \leq a_{i}, b_{i} \leq m$ 1 \leq a_i, b_i \leq m).

Вихідні дані

Виведіть $4$ цілі числа. $k$ -те з них має дорівнювати кількості впорядкованих пар $(i, j)$ з $1 \leq i, j \leq n$ 1 \leq i, j \leq n, для яких $f (i, j) = k$ f(i, j) = k.

Приклади

Приклад 1

Приклад 2

Примітка

Для послідовності з чотирьох чисел $p_{1}, p_{2}, p_{3}, p_{4}$ p_1, p_2, p_3, p_4 через НЗП $(p_{1}, p_{2}, p_{3}, p_{4})$ (p_1, p_2, p_3, p_4) позначимо довжину найдовшої строго зростаючої підпослідовності цієї послідовності.

У першому прикладі:

$f (1, 1) = НЗП (1, 2, 1, 2) = 2$ f(1, 1) = \text{НЗП}(1, 2, 1, 2) = 2.
$f (1, 2) = НЗП (1, 2, 3, 4) = 4$ f(1, 2) = \text{НЗП}(1, 2, 3, 4) = 4.
$f (2, 1) = НЗП (3, 4, 1, 2) = 2$ f(2, 1) = \text{НЗП}(3, 4, 1, 2) = 2.
$f (2, 2) = НЗП (3, 4, 3, 4) = 2$ f(2, 2) = \text{НЗП}(3, 4, 3, 4) = 2.

У другому прикладі всі числа рівні, тому ми не змогли б обрати жодної зростаючої підпослідовності довжиною щонайменше $2$ .