← 返回题目列表

AtCoder · abc306_f

I. 合并集

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

分数: 525 点

问题陈述

对于两组整数, A 和 B,这样 A \cap B = \emptyset,我们定义 f(A,B) 如下。

  • 让 C=(C_1,C_2,\dots,C_{|A|+|B|}) 是由以下元素组成的序列 A \cup B,按升序排序。
  • 采取 k_1,k_2,\dots,k_{|A|} 这样 A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace。 然后,让 \displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i.

例如,如果 牌匾上写着 A=\lbrace 1,3\rbrace 和 B=\lbrace 2,8\rbrace,那么 C=(1,2,3,8),所以 A=\lbrace C_1,C_3\rbrace;因此, f(A,B)=1+3=4.

我们有 N 整数集, S_1,S_2\dots,S_N,每个都有 M 元素。 对于每个 i\ (1 \leq i \leq N), S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace。 在此,可以保证 S_i \cap S_j = \emptyset\ (i \neq j).

查找 \displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j).

约束

  • 1\leq N \leq 10^4
  • 1\leq M \leq 10^2
  • 1\leq A_{i,j} \leq 10^9
  • If i_1 \neq i_2 or j_1 \neq j_2,那么 A_{i_1,j_1} \neq A_{i_2,j_2}.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_{1,1} A_{1,2} \dots A_{1,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}

输出

将答案打印为整数。


示例输入 1

3 2
1 3
2 8
4 6

示例输出 1

12

S_1 和 S_2 分别符合 A 和 B 在问题陈述中举例说明,并且 f(S_1,S_2)=1+3=4。 自从 f(S_1,S_3)=1+2=3 和 f(S_2,S_3)=1+4=5,答案是 4+3+5=12.


示例输入 2

1 1
306

示例输出 2

0

示例输入 3

4 4
155374934 164163676 576823355 954291757
797829355 404011431 353195922 138996221
191890310 782177068 818008580 384836991
160449218 545531545 840594328 501899080

示例输出 3

102