New Year and Ascent Sequence

题意翻译

### 题意简述 给定 $n$ 个整数序列 $s_1,s_2,...,s_n$。 我们可以把两个长分别为 $lx$ 和 $ly$ 的序列 $s_a,s_b$ 拼接起来，拼接后的序列是 $[s_{a,1},s_{a,2},...,s_{a,lx},s_{b,1},s_{b,2},...,s_{b,ly}]$。 容易发现，如果在 $n$ 个序列中任选两个拼起来，一共有 $n^2$ 种拼法。 现在问你在 $n^2$ 种拼法拼成的序列中有多少个拼成的长度为 $l$ 的序列 $a$，使得存在 $(i,j)$ 满足 $1\leq i<j \leq l$ 且 $a_i<a_j$ 。 ### 输入格式 第一行一个正整数 $n(1\leq n \leq 10^5)$。 接下来 $n$ 行，每行的第一个正整数 $l_i(1\leq l_i)$ 表示第 $i$ 个序列的长度。接下来 $l_i$ 个整数 $s_{i,1},s_{i,2},...,s_{i,l_i}(1\leq s_i \leq 10^6)$。 $\sum l_i$ 不会超过 $10^5$。 ### 输出格式 输出一行，表示满足条件的序列数量。

题目描述

A sequence $ a = [a_1, a_2, \ldots, a_l] $ of length $ l $ has an ascent if there exists a pair of indices $ (i, j) $ such that $ 1 \le i < j \le l $ and $ a_i < a_j $ . For example, the sequence $ [0, 2, 0, 2, 0] $ has an ascent because of the pair $ (1, 4) $ , but the sequence $ [4, 3, 3, 3, 1] $ doesn't have an ascent. Let's call a concatenation of sequences $ p $ and $ q $ the sequence that is obtained by writing down sequences $ p $ and $ q $ one right after another without changing the order. For example, the concatenation of the $ [0, 2, 0, 2, 0] $ and $ [4, 3, 3, 3, 1] $ is the sequence $ [0, 2, 0, 2, 0, 4, 3, 3, 3, 1] $ . The concatenation of sequences $ p $ and $ q $ is denoted as $ p+q $ . Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has $ n $ sequences $ s_1, s_2, \ldots, s_n $ which may have different lengths. Gyeonggeun will consider all $ n^2 $ pairs of sequences $ s_x $ and $ s_y $ ( $ 1 \le x, y \le n $ ), and will check if its concatenation $ s_x + s_y $ has an ascent. Note that he may select the same sequence twice, and the order of selection matters. Please count the number of pairs ( $ x, y $ ) of sequences $ s_1, s_2, \ldots, s_n $ whose concatenation $ s_x + s_y $ contains an ascent.

输入输出格式

输入格式

The first line contains the number $ n $ ( $ 1 \le n \le 100\,000 $ ) denoting the number of sequences. The next $ n $ lines contain the number $ l_i $ ( $ 1 \le l_i $ ) denoting the length of $ s_i $ , followed by $ l_i $ integers $ s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i} $ ( $ 0 \le s_{i, j} \le 10^6 $ ) denoting the sequence $ s_i $ . It is guaranteed that the sum of all $ l_i $ does not exceed $ 100\,000 $ .

输出格式

Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

输入输出样例

输入样例 #1

5
1 1
1 1
1 2
1 4
1 3

输出样例 #1

9

输入样例 #2

3
4 2 0 2 0
6 9 9 8 8 7 7
1 6

输出样例 #2

7

输入样例 #3

10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100

输出样例 #3

72

说明

For the first example, the following $ 9 $ arrays have an ascent: $ [1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4] $ . Arrays with the same contents are counted as their occurences.