分析
观察要求的式子：\(\sum_{1 \leq i \lt j \leq N}f(S_i, S_j)\)，发现可以拆成每一个集合 \(S_i\) 的贡献的和。那么我们考虑每一个集合 \(S_i\) 的贡献。
显然，对于每一个 \(S_i\) ，其贡献就是 \(\sum_{i \lt j \leq N}f(S_i, S_j)\)，也就是它与其后每一个集合 \(S_j\) 的 \(f\) 函数值相加。那么现在我们来深入剖析一下 \(f(A, B)\) 到底是什么。
观察题目描述 \(f(A,B)\) 的例子：
For example, if A = {1, 3} and B = {2, 8}, then C = (1, 2, 3, 8), so A = {C1, C3}; Thus, f(A, B) = 1 + 3 = 4.
这个例子告诉我们 \(f\) 的函数值实际上可以看成集合 \(A\) 中每个元素对其造成的贡献的和。
上结论：\(f(A, B)\) 的函数值是 \(A\) 中所有元素 在两个集合并起来的所有数 中的排名 的和。这个看例子应该就能明白了。考虑排名的定义：数列中 比某个数小的数 的个数 加一。定义 \(R(S, x)\) 为集合 \(S\) 中比 \(x\) 小的数的个数。那么 \(f(A, B)\) 可以被表示为
\(\sum_{1 \leq i \leq |A|}(R(A \cap B, A_i)+1).\)
由于 \(A\) 和 \(B\) 的交集是空集，所以可以将上式拆开：
\(f(A, B) = \sum_{1 \leq i \leq |A|}(R(A, A_i) + R(B, A_i)+1).\)
看到第二项 \(R(B, A_i)\)，立刻想到在值域上建立树状数组。于是前一项也就好搞了。做法：先把 \(B\) 里的每个元素扔到树状数组里，然后按顺序扫过 \(A\) 的每个元素，先查询比这个元素小的数 的个数 加到 \(ans\) 里，然后把这个元素也扔到树状数组里。扫完之后 \(ans\) 就是 \(f(A, B)\) 的值。
现在来发掘一下 \(f\) 函数的性质。
注：以下所指的任意两个集合 互相的交集 都是空集
$f(A, B) + f(A, C) = $
\(\sum_{1 \leq i \leq |A|}(R(A, A_i) + R(B, A_i)+1) + \sum_{1 \leq i \leq |A|}(R(A, A_i) + R(C, A_i)+1)\)
\(=\sum_{1 \leq i \leq |A|}(2R(A, A_i) + R(B, A_i) + R(C, A_i) + 2)\)
\(=\sum_{1 \leq i \leq |A|}(2R(A, A_i)+R(B \cap C, A_i)+2)\)
\(=2|A| + \sum_{1 \leq i \leq |A|}(2R(A, A_i) + R(B \cap C, A_i)).\)
同样的，这种性质也可以扩展到多个加数的情况，只要所有加数的第一个参数都是同一个集合：
\(f(A, S_1) + f(A, S_2) + f(A, S_3) + ... + f(A, S_n)\)
\(= n|A| + \sum_{1 \leq i \leq |A|}(nR(A, A_i) + R(S_1 \cap S_2 \cap S_3 ... \cap S_n, A_i)).\)
那么现在来考虑单个集合 \(S_i\) 的贡献 \(\sum_{i \lt j \leq N}f(S_i, S_j)\)。
\(\sum_{i \lt j \leq N}f(S_i, S_j)\)
\(=f(S_i, S_{i + 1})+f(S_i, S_{i+2})+...+f(S_i, S_N)\)
\(=(N-i)|S_i|+\sum_{1\leq j \leq m}((N-i)R(S_i, S_{i_j})+R(S_{i+1} \cap S_{i+2} \cap ... S_N, S_{i_j})).\)
如果将 \(S_i\) 排序后从前往后扫，那么 \(R(S_i, S_{i_j})\) 其实就等于 \(j - 1\)。所以上式
\(=(N-i)|S_i|+\sum_{1\leq j \leq m}((N-i)(j-1)+R(S_{i+1} \cap S_{i+2} \cap ... S_N, S_{i_j})).\)
求和号中的第一项好算。而第二项其实是每一个 \(S_{i_j}\) 在 其后所有集合 的并 中的排名。我们倒序扫每个集合，从小到大扫集合里的每个数，和之前一样树状数组即可。
这里有一点需要注意的是由于我们每次处理完一个元素之后就会将其扔进树状数组里，故该集合的后续元素 会将这个元素考虑进其贡献。但是这种集合内部的贡献是不在刚才那个和式的第二项中的。我们考虑其大小，发现第 \(j\) 个元素收到的这种贡献实际上就是 \(j - 1\)。于是可以直接把它跟第一项合并。
代码
#include <iostream>
#include <algorithm>
#include <map>
#define int long long
#define lowbit(x) ((x) & -(x))
using namespace std;
int a[10005][105];
int d[1000005];
int bit[1000005];
void add(int x) { for (; x <= 1000000; x += lowbit(x)) bit[x]++; }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret += bit[x];
return ret;
}
map<int, int> mp;
signed main() {
int n, m, cnt = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
d[++cnt] = a[i][j];
}
sort(a[i] + 1, a[i] + m + 1);
}
int ans = 0;
sort(d + 1, d + cnt + 1);
for (int i = 1; i <= cnt; i++) mp[d[i]] = i; // 只会用 map 离散化的屑（指我
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= m; j++) {
a[i][j] = mp[a[i][j]];
ans += query(a[i][j]) + (j - 1) * (n - i - 1); // n - i 减去 1 就是为了应对集合内贡献
// query(a[i][j]) 就是和式里的第二项
add(a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
ans += m * (n - i); // 和式前面的项
}
cout << ans;
return 0;
}