RUPC 2016 day3 D: Complex Oracle

[l,r] と書いたら区間 [l,r] に対するクエリ結果と表すものとする。

[1,i] と [i,n] の結果をすべて求めておく。

i よりも左側にある a[i] より大きい要素の個数は [1,i]-[1,i-1] で求まる。このことから a[i] より小さい要素の個数は i-1-([1,i]-[1,i-1]) であることが分かる。

i よりも右側にある a[i] より小さいの要素の個数は [i,n]-[i+1,n] で求まる。

なので、これで全ての a[i] が求められる。

転倒数だったらしい。気が付かなかった。