@@ -4,13 +4,18 @@ title: Число инверсий
 weight: 5
 authors:
 - Сергей Слотин
+draft: true
 ---
 
-Пусть у нас есть некоторая перестановка $p$ (какая-то последовательность чисел от $1$ до $n$, где все числа встречаются ровно один раз). *Инверсией* называется пара индексов $i$ и $j$ такая, что $i < j$ и $p_i > p_j$. Требуется найти количество инверсий в данной перестановке.
+**Определение.** *Инверсией* в перестановке $p$ называется пара индексов $i$ и $j$ такая, что $i < j$ и $p_i > p_j$.
 
-## Наивный алгоритм
+Например:
 
-Эта задача легко решается за $O(n^2)$ обычным перебором всех пар индексов и проверкой каждого на инверсию:
+- в перестановке $[1, 2, 3]$ инверсий нет,
+- в $[1, 3, 2]$ одна инверсия ($3 \leftrightarrow 2$),
+- в $[3, 2, 1]$ три инверсии ($3 \leftrightarrow 2$, $3 \leftrightarrow 1$ и $2 \leftrightarrow 1$).
+
+В этой статье мы рассмотрим, как находить количество инверсий в перестановке. Эта задача легко решается за $O(n^2)$ обычным перебором всех пар индексов и проверкой каждого на инверсию:
 
 ```cpp
 int count_inversions(int *p, int n) {
@@ -23,6 +28,8 @@ int count_inversions(int *p, int n) {
 }
 ```
 
+Решить её быстрее сложнее.
+
 ## Сортировкой слиянием
 
 Внезапно эту задачу можно решить сортировкой слиянием, слегка модифицировав её.