Music Festival
Contest: Codeforces Round 857 (Div. 1)
Difficulty rating: 1900
Tags: binary search, data structures, dp, greedy, sortings

Vitya has a friend Masha, whom he really wants to invite to the festival, where his favorite bands perform. However, in order for a friend to agree, she must first evaluate the released novelties. Vitya knows that if Masha listens to a track that was cooler than all the previous ones, she will get 1 unit of impression. Unfortunately, albums can only be listened to in their entirety, without changing the songs in them in places.

Help Vitya find such an order of albums so that Masha's impression turns out to be as much as possible, and she definitely went to the festival with him.

Input format:
Each test consists of multiple test cases. The first line contains a single integer t ($$$1 \le t \le 200\,000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — number of albums.

The album descriptions follow. Each album description consists of two lines:

The first line contains a single integer $$$k_i$$$ ($$$1 \le k_i \le 200\,000$$$) — the number of tracks in the $$$i$$$th album.

The following line contains $$$k_i$$$ integers $$$a_{i, 1},\ a_{i, 2},\ a_{i, 3},\ \ldots,\ a_{i, k_i}$$$ ($$$1 \le a_{i,j} \le 200\,000$$$) — the coolness of the tracks in the $$$i$$$ album.

Denote for $$$\sum k_i$$$ the sum of all $$$k_i$$$. It is guaranteed that $$$\sum k_i \le 200\,000$$$.

Output format:
For each test case print the singular number  — the maximum impression that Masha can get.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first test example, the optimal order is listening to the 4th, 2nd, 3rd and 1st albums.

In this case, Masha will listen to the tracks in the following order: 1; 7; 8, 6; 4, 9, 4, 6, 8 and will receive 4 units of impression.

In the second test example, you must first listen to the 1st, then the 4th, and in any order the 2nd and 3rd.   In this case, Masha will get the maximum impression, and for every song in the 1st and 4th albums and nothing for the 2nd and 3rd.

Example input:
2
4
5
4 9 4 6 8
1
7
2
8 6
1
1
4
2
3 4
2
1 8
2
2 8
2
7 9

Example output:
4
4

Editorial:
Введём для альбома понятие сжатого альбома , который получается из исходного путём удаления всех элементов, кроме тех, которые являются первыми максимумами на соответствующих им префиксах.
К примеру:
Для альбома $$$[\textbf{1}, \textbf{4}, 4, 3, \textbf{6}, 5, 6]$$$ сжатым будет альбом $$$[1, 4, 6]$$$.
Теперь заметим, что решение исходной задачи сводится к решению этой же задачи, но на сжатых альбомах. Действительно, ответ на них не будет отличаться, ведь если какой-то элемент увеличивал впечатление на обычных альбомах, то он будет увеличивать, если сжать альбомы и наоборот. Далее будет считаться, что предварительно все альбомы были сжаты.
1 подгруппа Можно просто перебрать порядок в котором Маша будет слушать альбомы и для каждого порядка посчитав количество впечатления, которое она получит и взять максимум из этих величин. Решение за $$$O(n! K)$$$
2 подгруппа Заметим, что ответ равен 2, если есть сжатый альбом $$$[1, 2]$$$ или есть сжатые альбомы $$$[1]$$$ и $$$[2]$$$, в ином случае ответ 1. Решение за $$$O(K)$$$
5 подгруппы Отсортируем сжатые альбомы в порядке увеличения последнего числа. Заметим, что если Маша послушала альбом с номером $$$i$$$, то все альбомы с номерами меньше дадут 0 единиц впечатления. Теперь можно посчитать следующую динамику. $$$dp_i$$$ — количество впечатления, при условии, что Маша послушала последним $$$i$$$-й альбом. При пересчёте $$$dp_i$$$ через $$$dp_j$$$ надо посчитать количество, элементов в $$$i$$$-м альбоме, что они больше, чем максимальный в $$$j$$$-м. Решение за $$$O(n^2 \log K)$$$, если использовать бинарный поиск.
3 подгруппа Существует не более чем $$$2^C$$$ различных вариантов сжатых альбомов. Тогда удалив одинаковые сжатые альбомы и, применив решение для $$$5$$$-й подзадачи, можно получить решение за $$$O(4^C \log K)$$$.
4 подгруппа Введём $$$dp_c$$$ — максимум впечатления, которое можно получить, если бы не было альбомов, таких, что в них есть элементы большие, чем $$$c$$$. Тогда, $$$dp_c$$$ равно $$$dp_{c-1}$$$, либо можно добавить ещё элемент или два, если в $$$c$$$ является максимальным элементом для какого-то альбом. Тогда для всех сжатых альбомов, можно пересчитаться через значение $$$dp$$$ в точке перед первым элементом альбома, либо через $$$c - 1$$$. Таким образом для пересчёта достаточно знать для каждого $$$c$$$ какие альбомы закончились в этом индексе, а так же для каждого альбома его первый элемент. Решение за $$$O(K)$$$
Полное решение Обобщим идею предыдущих подгрупп. Для каждого значения $$$c$$$ запомним индексы альбомов, которые содержат элемент равный $$$c$$$. Идём в порядке увеличения $$$c$$$, поддерживаем для каждого альбома значение $$$dp_i$$$ — максимум впечатления, который можно получить если бы не было элементов больших $$$c$$$ и Маша послушала последним $$$i$$$-й альбом. Пусть для очередного $$$c$$$ существует альбом $$$i$$$, что в нём есть песня с крутостью $$$c$$$. Тогда $$$dp_i$$$ надо взять максимумом из $$$dp_i + 1$$$ и значения по всем $$$dp_j + 1$$$, таких, что максимальный элемент в $$$j$$$-м альбоме меньше чем максимальный элемент $$$i$$$-го, так как она могла послушать этот трек, либо следующим в этом альбоме, либо после того, как послушала какой-то другой альбом полностью. Заметим, что можно хранить значение $$$mx$$$ — максимум по всем альбомам, для которых максимальное значение в них меньше $$$c$$$ и пересчитывать его при переходе к $$$c + 1$$$, храня те альбомы, которые закончились, тогда получится решение за $$$O(K + C)$$$.