T1
给定长度为 \(n\) 的数组 \(a, b, c\)，求
\[\sum\limits_{i = 1} ^ n \sum\limits_{j = i + 1} ^ n \max(a_i - a_j, b_i - b_j, c_i - c_j) - \min(a_i - a_j, b_i - b_j, c_i - c_j) \]\(n \leq 5 \times 10 ^ 5\)，时限 \(\texttt{500ms}\)。
\(\text{min-max}\) 容斥：$\max(S) = \sum\limits_{T \subseteq S} (-1) ^ {|T| + 1} \min(T) $。
然后直接套进去，变成 \(\sum\limits_{i = 1} ^ n \sum\limits_{j = i + 1} ^ n -\min(a_i - a_j, b_i - b_j) - \min(a_i - a_j, c_i - c_j) - \min(b_i - b_j, c_i - c_j) + (a_i - a_j) + (b_i - b_j) + (c_i - c_j)\)，然后直接树状数组。
怎么不打 \(2\log\) 暴力啊。
Code of T1
#include <bits/stdc++.h>
const int M = 5e5 + 10, mod = 1e9 + 7;
inline int read() {
char ch = getchar();
int x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int n, a[M], b[M], c[M], f[M], lsh[M], len;
long long ans;
struct BIT {
long long t[M];
inline void reset() {
for (int i = 1; i <= n; i++) t[i] = 0;
}
inline void add(int x, int v) {
for (; x <= n; x += (x & -x)) t[x] += v;
}
inline long long qry(int x) {
long long ret = 0;
for (; x; x -= (x & -x)) ret += t[x];
return ret;
}
} T1;
inline void LSH(int* x) {
len = 0;
for (int i = 1; i <= n; i++) lsh[++len] = x[i];
std::sort(lsh + 1, lsh + 1 + len);
len = std::unique(lsh + 1, lsh + 1 + len) - lsh - 1;
for (int i = 1; i <= n; i++)
x[i] = std::lower_bound(lsh + 1, lsh + 1 + len, x[i]) - lsh;
}
inline void calc(int* x, int* y) {
for (int i = 1; i <= n; i++) f[i] = x[i] - y[i];
LSH(f);
T1.reset();
for (int i = n; i >= 1; i--) {
ans -= x[i] * (n - i - T1.qry(f[i]));
ans -= y[i] * T1.qry(f[i]);
T1.add(f[i], 1);
}
T1.reset();
for (int j = 1; j <= n; j++) {
ans += x[j] * T1.qry(f[j] - 1);
ans += y[j] * (j - 1 - T1.qry(f[j] - 1));
T1.add(f[j], 1);
}
}
int main() {
n = read();
for (int i = 1; i <= n; i++)
a[i] = read(), b[i] = read(), c[i] = read();
for (int i = 1; i <= n; i++)
ans += 1ll * (n - i - i + 1) * (a[i] + b[i] + c[i]);
calc(a, b), calc(b, c), calc(c, a);
printf("%lld\n", ans % mod);
return 0;
}