ABC231F
まず，求める答えを式に直してみる． \(i,j \in N\) であって \(a_{i} \geq a_{j}\) かつ \(b_{j} \geq b_{i}\) となる 組\(\,(i,j)\) の個数を数える． \(b\) はマイナスを掛けて順序を反転させると， \(a\) と同じ形になって楽．
平面走査で数える． \(a\) を小さい順に調べれば， \(a_{i} \leq a_{j}\) の条件は自動的に満たす． 言い換えると， \(a_{i}\) について調べている時点で， \(a_{i} > a_{j}\) となる \(j\) は過不足なく調べ終わっている． \(=\) の場合だけ注意． 平面走査のおかげで，求めるべきは \(b_{i} \geq b_{j}\) となる \(j\) の個数に簡略化できた．
実装
点\(\,(a_{i}, b_{i})\) をプロットする． 同じ点があるので，個数も数えておく． また， \(b_{i} \geq b_{j}\) となる \(j\) の個数は segtree で数え上げるとよい．
また， \(a,b\) の値は大きいので座標圧縮する． 実際は，segtreeに乗せる \(b\) の方だけ圧縮すれば十分．
別解
数え上げる方法として，各 \(a_{i}\) に対して， \(\,(a_{j}, b_{j})\) かつ \(a_{j} = a_{i}\) となる \(j\) 全体を求めておく方法もある． これは，加算クエリと数えるクエリを分けることで解決できる． この場合もsegtreeで \(j\) を数え上げる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename P>
struct Points {
Points() {}
// void add(const P& x) {
// ps.push_back(x);
// }
void add(P x) {
ps.emplace_back(x);
}
void init() {
sort(ps.begin(), ps.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
}
P operator[](int i) const { return ps[i];}
int operator()(const P& x) const {
return lower_bound(ps.begin(),ps.end(), x)-ps.begin();
}
int size() const { return ps.size();}
};
ll op(ll a,ll b) { return a+b; }
ll e() {return 0; }
int main() {
ll n, m ;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
vll b(n); cinv(b);
rep(i,n){
b[i] *= -1;
pb.add(b[i]);
}
pb.init();
map<pll,ll> mp;
rep(i,n){
mp[{pa(a[i]), pb(b[i])}]++;
}
segtree<ll, op, e> st(pb.size());
ll ans = 0;
for(auto [ab, cnt]: mp){
auto [_,y] = ab;
st.set(y, st.get(y) + cnt);
ans += st.prod(0,y+1) * cnt; // rem : *cnt
}
cout << ans << endl;
return 0;
}
