AT_past202010_k.転倒数

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $k$ 个数列，第 $i$ 个数列被称为 $a_i$ 。它有 $n_i$ 个数，第 $j$ 个数是 $a_{i,j}$ 。

同时，还有一个数列 $x$ 。 $x$ 最初为空。

现在有 $q$ 次操作。每次操作会给出一个整数 $b_i$ ，表示将 $a_{b_i}$ 连接到 $x$ 的后面。

所有操作完成后，请你求出有多少个整数对 $(i,j)$ 满足： $1 \le i \lt j \le |x|$ 且 $x_i \gt x_j$ ？结果可能会很大，所以对 $10^9$ 取模。（ $|x|$ 表示 $x$ 的长度）

输入格式

第一行，一个正整数 $k$ 。

接下来 $2k$ 行，第 $2i-1$ 行输入的是 $n_i$ ，第 $2i$ 行输入的是 $a_{i,j}$ 。

接下来一行，一个正整数 $q$ 。

接下来一行， $q$ 个正整数，表示数列 $b$ 。

输出格式

输出结果对 $10^9$ 取模后的值。

输入输出样例

输入#1
```
2
3
1 3 2
2
5 4
2
1 2
```
输出#1
```
2
```

输入#2

10
8
16 6 15 10 18 13 17 11
13
4 10 6 4 14 17 13 9 3 9 4 8 14
11
11 17 12 3 13 8 10 11 18 2 19
10
18 11 16 19 4 17 7 3 5 8
3
3 10 9
13
8 17 20 8 20 1 5 17 4 16 18 20 4
15
11 2 1 16 8 17 4 7 3 6 4 13 16 16 16
2
12 12
8
7 14 7 5 8 17 19 4
15
3 6 1 16 11 5 3 15 9 15 12 15 5 19 7
20
4 3 7 6 1 8 2 3 9 8 6 3 10 9 7 7 3 2 2 10

输出#2

说明/提示

$1 \le k,q,n_i \le 10^5$ ， $1 \le a_{i,j} \le 20$ ， $1 \le b_i \le k$ ，所有 $n_i$ 之和 $\le 3 \times 10^5$ 。

输入解题思路，AI测评打分。不知道怎么写?

首页