标签：扫描线、树状数组、线段树
题意：给定序列$A$，计算$\sum _{i=1}^N\sum _{j=i+1}^N\max (A_j-A_i,0)$
题解：观察公式，我们按照顺序遍历序列$A$中的数，固定$A_j$，就变成了求当前数字和前面所有比自己小的数字之差的和。即公式：$\sum _{i=1}^{j-1}{A}_j-A_i$在满足条件$A_j>A_i$的情况下。
我们将这个式子展开：$A_j\sum _{i=1}^{j-1}-\sum _{i=1}^{j-1}{A}_i$在满足条件$A_j>A_i$的情况下。
通俗点讲，假设对于$A_j$来说，在它前面有$m$个比它小的数$A_i$，那么值就是$m$个$A_j$之和减去所有在第$j$个数之前比它小的$A_i$之和。这个东西可以通过树状数组或者线段树进行维护。这题数据量比较大，需要离散化处理下。
代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll N = 4e5 + 10;
ll n, b[N], num[N], sum[N], ans = 0;
struct node {ll a, id;
}p[N];bool cmp1(node x, node y) {if (x.a == y.a) return x.id < y.id;return x.a < y.a;
}bool cmp2(node x, node y) {return x.id < y.id;
}ll lowbit(ll x) {return x & (-x);
}void update(ll *tree, ll x, ll k) {for (ll i = x; i <= n; i += lowbit(i)) tree[i] += k;
}ll query(ll *tree, ll x) {ll res = 0;for (ll i = x; i > 0; i -= lowbit(i)) res += tree[i];return res;
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> p[i].a;p[i].id = i;}sort(p + 1, p + 1 + n, cmp1);for (int i = 1; i <= n; i++) b[p[i].id] = i;sort(p + 1, p + 1 + n, cmp2);for (int i = 1; i <= n; i++) {ans += p[i].a * query(num, b[i] - 1);ans -= query(sum, b[i] - 1);update(num, b[i], 1);update(sum, b[i], p[i].a);}cout << ans;return 0;
}