开始: 2025-07-05 17:45:00

暑期训练赛04

结束: 2025-07-05 20:30:00
当前  2025-07-17 21:32:34  类型: IOI  状态: 已经结束 

P2. 唱跳RAP
描述

吴老师 拿到了 n 个篮球,从 1n 分别编号,第 i 个篮球的重量为 a_i

Kitten 抢走了 m 个篮球,抢走的篮球编号分别为 b_1\sim b_m

吴老师 想要在剩下的篮球中挑出两个一样重的,请问有多少种方案?


输入

第一行一个整数 n,m

第二行为空格隔开的 a_1\sim a_n

第三行为空格隔开的 b_1\sim b_m


输出

一行一个整数,表示方案数量。

样例

输入

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

输出

7
提示

样例解释

`1 1 (2) 2 (1) 1 1 3 (3) 2`

拿走了第 3、第 5 和第 9 个篮球后,剩下的为:

`1 1 2 1 1 3 2`

要拿走两个一样的篮球

- 拿走两个重量为 1 的篮球有 6 种方案。

- 拿走两个重量为 2 的篮球有 1 种方案。

一共有 7 种方案。


数据规模与约定

对于 100\% 的数据,0 \le m\le n \le 10001\le a_i\le 1001\le b_i\le n

- 子任务 1(30 分):m=0

- 子任务 2(30 分):a_i=1

- 子任务 3(40 分):没有特殊限制。


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交