算法分析
一句话题意:求 $\sum\limits_{i=1}^N\sum\limits_{j=1}^N [A_j \leqslant A_i ~\operatorname{且} ~B_i \leqslant B_j]$
注意到 $B_i \leqslant B_j \Leftrightarrow -B_j \leqslant -B_i$,做这种转化后,就可以使得 $B$ 的大小关系和 $A$ 是一致的
然后就是典型的二维数点问题,做法有很多,比如离散化+树状数组/线段树,或者 CDQ分治
等
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<int> A(n), B(n);
rep(i, n) cin >> A[i];
rep(i, n) cin >> B[i];
map<int, int> mp;
map<int, vector<int>> d;
rep(i, n) {
int a = A[i], b = B[i];
b = -b;
d[a].push_back(b);
mp[b] = 0;
}
{
int i = 0;
for (auto&& p : mp) {
p.second = i++;
}
}
int m = mp.size();
fenwick_tree<int> t(m);
ll ans = 0;
for (auto [_, bs] : d) {
for (int b : bs) {
b = mp[b];
t.add(b, 1);
}
for (int b : bs) {
b = mp[b];
ans += t.sum(0, b+1);
}
}
cout << ans << '\n';
return 0;
}