← 返回题目列表

Codeforces · 1284/B

B. 新年和上升序列

中文机器翻译题面 查看原题

如果存在一对索引 $$$(i, j)$$$ 使得 $$$1 \le i < j \le l$$$ 且 $$$a_i < a_j$$$,则长度 $$$l$$$ 的序列 $$$a = [a_1, a_2, \ldots, a_l]$$$ 具有上升趋势。例如,序列 $$$[0, 2, 0, 2, 0]$$$ 由于 $$$(1, 4)$$$ 对而具有上升趋势,但序列 $$$[4, 3, 3, 3, 1]$$$ 没有上升趋势。

让我们将序列 $$$p$$$ 和 $$$q$$$ 的串联称为通过连续写下序列 $$$p$$$ 和 $$$q$$$ 而不改变顺序而获得的序列。例如,$$$[0, 2, 0, 2, 0]$$$ 和 $$$[4, 3, 3, 3, 1]$$$ 的串联是序列 $$$[0, 2, 0, 2, 0, 4, 3, 3, 3, 1]$$$。序列 $$$p$$$ 和 $$$q$$$ 的串联表示为 $$$p+q$$$。

京根认为连续上升会带来好运。因此,他想在新的一年里拍很多这样的镜头。 Gunggeun 有 $$$n$$$ 序列 $$$s_1, s_2, \ldots, s_n$$$ 可能有不同的长度。

Gyeonggeun 将考虑所有 $$$n^2$$$ 序列对 $$$s_x$$$ 和 $$$s_y$$$ ($$$1 \le x, y \le n$$$),并检查其串联 $$$s_x + s_y$$$ 是否有上升。请注意,他可能会选择相同的序列两次,并且选择的顺序很重要。

请计算 $$$s_1, s_2, \ldots, s_n$$$ 的串联 $$$s_x + s_y$$$ 包含上升的序列对 ($$$x, y$$$) 的数量。

输入

第一行包含数字 $$$n$$$ ($$$1 \le n \le 100\,000$$$) 表示序列数。

接下来的 $$$n$$$ 行包含数字 $$$l_i$$$ ($$$1 \le l_i$$$) 表示 $$$s_i$$$ 的长度,后跟 $$$l_i$$$ 整数 $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i}$$$ ($$$0 \le s_{i, j} \le 10^6$$$) 表示序列 $$$s_i$$$。

保证所有$$$l_i$$$的总和不超过$$$100\,000$$$。

输出

打印一个整数,即串联有上升的序列对的数量。

示例

输入 #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

注意

对于第一个示例,以下 $$$9$$$ 数组具有上升:$$$[1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]$$$。具有相同内容的数组将被计为它们的出现次数。