Задача №115223. Рекорды и антирекорды
Перестановкой размера \(n\) называется последовательность \(n\) целых чисел \(a_1, a_2, \ldots, a_n\), в которой все значения от \(1\) до \(n\) встречаются ровно по одному разу.
Последовательность \(b_1, b_2, \dots, b_l\) является подпоследовательностью последовательности \(a_1, a_2, \dots, a_n\), если \(b\) можно получить из \(a\) удалением некоторых элементов (то есть \(l \le n\) и существуют \(i_1 < i_2 < \ldots < i_l\) такие что \(a_{i_t} = b_t\)).
- Элемент последовательности \(a_i\) называется рекордом , если он строго больше всех предыдущих элементов (то есть \(a_j < a_i\) для всех \(1 \le j < i\)).
- Элемент последовательности \(a_i\) называется антирекордом , если он строго меньше всех предыдущих элементов (то есть \(a_j > a_i\) для всех \(1 \le j < i\)).
Дана перестановка \(p_1, p_2, \dots, p_n\) размера \(n\). Требуется разделить её на две непустые подпоследовательности \(q\) и \(r\). Иными словами, каждый элемент \(p\) должен попасть ровно в одну из подпоследовательностей. При этом требуется максимизировать сумму количества рекордов в \(q\) и количества антирекордов в \(r\).
Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится единственное целое число \(t\) (\(1 \le t \le 100\,000\)) — количество наборов входных данных. В следующих \(2t\) строках следуют описания наборов входных данных.
В первой строке описания каждого набора входных данных содержится одно целое число \(n\) — размер перестановки (\(2 \le n \le 200\,000\)).
Во второй строке описания каждого набора входных данных содержатся \(n\) целых чисел \(p_1, p_2, \dots, p_n\) — исходная перестановка. Гарантируется, что среди элементов \(p\) каждое число от \(1\) до \(n\) встречается ровно по одному разу.
Сумма \(n\) по всем наборам входных данных не превосходит \(200\,000\).
Для каждого набора входных данных выведите одно целое число — максимальную возможную сумму количества рекордов в \(q\) и антирекордов в \(r\) в оптимальном разбиении.
Обозначим как \(N\) сумму значений \(n\) во всех наборах входных данных одного теста.
| Ограничения | |||||
| Подз. | Баллы | \(n\), \(N\) | Доп. ограничения | Необх. подзадачи | Информация о проверке |
| 1 | 21 | \(n \le 16\) | \(t \leq 120\) | У | первая ошибка |
| 2 | 22 | \(n \le 200\), \(N \leq 2000\) | У, 1 | первая ошибка | |
| 3 | 14 | \(N \le 2\,000\) | У, 1–2 | первая ошибка | |
| 4 | 10 | \(N \le 10\,000\) | У, 1–3 | первая ошибка | |
| 5 | 13 | \(N \le 200\,000\) | Длина наибольшей убывающей подпоследовательности в \(p\) не превышает \(2\) | первая ошибка | |
| 6 | 20 | \(N \le 200\,000\) | У, 1–5 | первая ошибка | |
Один из способов оптимальным образом разбить \(p\) на \(q\) и \(r\) в первом наборе входных данных (рекорды в \(q\) и антирекорды в \(r\) обведены):
- \(q = \boxed{1}~\boxed{2}~\boxed{3}~\boxed{5}\)
- \(r = \boxed{4}\)
Один из способов оптимальным образом разбить \(p\) на \(q\) и \(r\) во втором наборе входных данных:
- \(q = \boxed{3}~\boxed{8}~4~1~2~\boxed{9}\)
- \(r = \boxed{10}~\boxed{7}~\boxed{5}~6\)
4 5 4 1 2 3 5 10 3 8 10 4 1 2 7 9 5 6 3 1 2 3 6 4 2 5 1 6 3
5 6 3 5