読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

RUPC 2016 day3 D: Complex Oracle

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=D

解法

[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] = (a[i] より小さい要素の個数)+1

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

RUPC 2016 day3 D: Complex Oracle

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