题目描述

现在有两个班级，第一个班级有 $n$ 名学生，第二个班级有 $m$ 名学生，两个班级将合并成一个 $n+m$ 人的班级。

每名学生有一个考试成绩，根据成绩决定班级排名。合并班级不改变成绩。设一名学生原先在旧班级的排名为 $a$，在新班级的排名为 $b$，其落差值为 $(b-a)^2$。

求所有学生落差值之和。

排名规则：所有学生按成绩从低到高排序（成绩低的排名靠前）。成绩相同的学生排名相同，且该排名为「严格低于该成绩的人数 $+1$」。例如四个学生的成绩为 $3, 3, 4, 4$，排序后为 $[3, 3, 4, 4]$，排名依次为 $1, 1, 3, 3$。

输入格式

第一行两个正整数 $n, m$。

第二行 $n$ 个正整数，表示第一个班级的学生成绩。

第三行 $m$ 个正整数，表示第二个班级的学生成绩。

输出格式

一行一个整数，表示所有学生的落差值平方和。

3 4
1 2 3
1 3 4 5

24

1 2
2
1 2

1

1 1
100 100

0

样例解释

样例 $1$：合并后成绩排序为 $[1,1,2,3,3,4,5]$，排名依次为 $[1,1,3,4,4,6,7]$。

• 原班级一：成绩 $1,2,3$，旧排名 $1,2,3$；新排名 $1,3,4$。落差值：$(1-1)^2=0$，$(3-2)^2=1$，$(4-3)^2=1$。
• 原班级二：成绩 $1,3,4,5$，旧排名 $1,2,3,4$；新排名 $1,4,6,7$。落差值：$(1-1)^2=0$，$(4-2)^2=4$，$(6-3)^2=9$，$(7-4)^2=9$。 总和为 $0+1+1+0+4+9+9=24$。

样例 $2$：班级一只有一人成绩 $2$，旧排名 $1$。班级二两人成绩 $[1,2]$，旧排名 $[1,2]$。合并后成绩排序 $[1,2,2]$，排名 $[1,2,2]$。班级一学生新排名 $2$，落差 $(2-1)^2=1$。班级二两学生新排名与原排名相同，落差均为 $0$。总和为 $1$。

样例 $3$：两个班级各有一名成绩为 $100$ 的学生。合并前后排名不变，落差均为 $0$，总和为 $0$。

数据范围与约定

对于所有数据，$1 \le n, m \le 10^5$，学生成绩均为 $1 \sim 10^9$ 的整数。

下发样例

下发样例下载