\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
コストの最小を求めるが，下界を求めてそれを実現する例を与える． 下界を求める過程は，必要条件を求めるのに近い．
Sub problem: コスト無し
コストを無視して \(P_{i}\) と \(P_{i+1}\) の swap を考える． \(P\) を昇順にするには，小さい \(P_{i}\) から左に寄せていくと， 少ない回数でソートできる．
Sub problem: コスト有り
コストがある場合も，コスト無しの場合と似た方法で出来る． \(P_{[0,i)}\) までソートされているとして，\(i = P_{i}\) となるように並べ替えることを考える． このとき，最低でも掛かるコストを求める． 集合\(X\)を， \(i\) の左にある \(P\) の元のうち，\(i\) より大きい元全体 とする． \(i = P_{i}\) となるまで並べ替えるためには，最低 $$ \sum_{x \in X} (i + x) = |X|\cdot i + \sum X $$ かかる． 実際にこのコストでのソートが実現できるのは，コスト無し版の解法から分かる．
実装
この解法には，次が有れば十分． 任意の \(i \in N\) に対して，
- \(| \set{j \in i }{ P_{j} > P_{i} } | \),
- \(\sum \set{P_{j}}{ j \in i \ and \ P_{j} > P_{i} }\).
これらは，共に segtree で実現出来る．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll op(ll a, ll b){ return a+b; }
ll e() {return 0;}
int main() {
ll n;
cin >> n;
segtree<ll,op,e> perm(n);
segtree<ll,op,e> cnt(n);
vll pos(n+1);
rep(i,n){
ll x; cin >> x;
perm.set(i,x);
cnt.set(i,1);
pos[x] = i;
}
ll ans = 0;
rep1(i,n){
ll p = pos[i];
ans += perm.prod(0,p);
ans += cnt.prod(0,p) * i;
perm.set(p, 0);
cnt.set(p, 0);
}
cout << ans << endl;
return 0;
}
