103065: [Atcoder]ABC306 F - Merge Sets

Problem Statement

For two sets of integers, $A$ and $B$, such that $A \cap B = \emptyset$, we define $f(A,B)$ as follows.

• Let $C=(C_1,C_2,\dots,C_{|A|+|B|})$ be a sequence consisting of the elements of $A \cup B$, sorted in ascending order.
• Take $k_1,k_2,\dots,k_{|A|}$ such that $A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace$. Then, let $\displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i$.

For example, if $A=\lbrace 1,3\rbrace$ and $B=\lbrace 2,8\rbrace$, then $C=(1,2,3,8)$, so $A=\lbrace C_1,C_3\rbrace$; thus, $f(A,B)=1+3=4$.

We have $N$ sets of integers, $S_1,S_2\dots,S_N$, each of which has $M$ elements. For each $i\ (1 \leq i \leq N)$, $S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace$. Here, it is guaranteed that $S_i \cap S_j = \emptyset\ (i \neq j)$.

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

Constraints

• $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$, then $A_{i_1,j_1} \neq A_{i_2,j_2}$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

3 2
1 3
2 8
4 6

Sample Output 1

12

$S_1$ and $S_2$ respectively coincide with $A$ and $B$ exemplified in the problem statement, and $f(S_1,S_2)=1+3=4$. Since $f(S_1,S_3)=1+2=3$ and $f(S_2,S_3)=1+4=5$, the answer is $4+3+5=12$.

Sample Input 2

1 1
306

Sample Output 2

0

Sample Input 3

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

Sample Output 3

102

问题描述

对于两个整数集合A和B，使得A和B的交集为空，我们定义f(A,B)如下。

• 令C=(C1,C2,...,|A|+|B|)是一个由A和B的元素组成的序列，按升序排列。
• 取k1,k2,...,|A|使得A={Ck1,Ck2,...,C|A|}。 然后，令f(A,B)=∑i=1|A|ki。

例如，如果A={1,3}且B={2,8}，那么C=(1,2,3,8)，所以A={C1,C3}；因此，f(A,B)=1+3=4。

我们有N个整数集合S1,S2,...,SN，每个集合都有M个元素。 对于每个i(1≤i≤N)，Si={Ai,1,Ai,2,...,Ai,M}。 这里，保证S1∩Sj=∅(i≠j)。

求∑1≤i

约束条件

• 1≤N≤104
• 1≤M≤102
• 1≤Ai,j≤109
• 如果i1≠i2或j1≠j2，则Ai,1≠Ai,2。
• 所有输入值都是整数。

输入

输入从标准输入按以下格式给出：

N M
A1,1 A1,2 ... A1,M
vdots
AN,1 AN,2 ... AN,M

输出

将答案作为一个整数打印。

样例输入1

3 2
1 3
2 8
4 6

样例输出1

12

S1和S2分别与问题描述中示例中的A和B相同，且f(S1,S2)=1+3=4。 由于f(S1,S3)=1+2=3且f(S2,S3)=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