4032 - 借书

题目描述

在绿洲市的图书馆中,管理员小 A 负责管理一排编号从 1N 的书籍,第 i 本书的分类编号为 C_i。每本书的分类编号唯一,同一个分类编号的图书可能会有多本。

由于图书馆正在进行整理,小 A 发现有 M 本书被读者借走,借走的书籍编号为 B_1 \sim B_m

现在,小 B 想要从剩余的书籍中挑选两本属于同一类别的书籍(即:分类编号相同)。

请问小 B 有多少种挑选方案?

输入

第一行读入两个整数 N, M,分别表示书籍总数和被借走的书籍数量。

第二行读入 N 个整数 C_1 \sim C_n,表示每本书的分类编号。

第三行读入 M 个整数 B_1 \sim B_m,表示被借走的书籍编号。

输出

输出一个整数,表示小 B 可能挑选两本同一类别书籍的方案数。

样例

输入

10 3
1 1 2 2 1 1 1 3 3 2
3 5 9

输出

7

输入

12 0
1 2 2 1 3 3 1 1 2 3 1 2

输出

19

输入

16 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 4 6 8 10

输出

55
说明

样例 1 说明

初始书籍类别序列为:

1 1 2 2 1 1 1 3 3 2

被借走的书籍编号为 359,对应类别编号为 2, 1, 3

剩余书籍的类别序列为:

1 1 2 1 1 3 2

小 B 需要挑选两本同类别的书籍:

  • 类别 1 的书籍有 4 本(在剩余书籍中的位置为 1, 2, 4, 5),挑选两本有 6 种方案。
  • 类别 2 的书籍有 2 本(在剩余书籍中的位置为 3, 7),挑选两本有 1 种方案。
  • 类别 3 的书籍只有 1 本,无法挑选两本。

总方案数:6 + 1 = 7

数据范围与约定

对于 100\% 的数据满足 0 \leq M \leq N \leq 10001 \leq C_i \leq 1001 \leq B_i \leq N

测试点编号特殊性质
30\% 的数据M=0
另外 30\% 的数据C_i=1
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题