問題概要
数列があって、一ペア交換したときの転倒数の最小値を求めよ
小課題1
aとbを交換するとき(aがもともと左、a>b)、aとbの間にある数について、aと同じなら1、bと同じなら1、a>x>bなら2だけ転倒数が減る。
任意のペアについて確かめると、O(N^2)回領域内の点の個数を求めることになる。
いもす法で前処理O(N^2)、クエリO(1)
セグ木に可変長配列を持たせて二分探索すると前処理O(NlogN)、クエリO(logN)
とかをやると解ける
小課題2
分からない
小課題3
分からない
小課題4
まず、左上に他の点がない集合Aと右下に他の点がない集合Bをつくる。それぞれ狭義単調増加の形になっていて、集合Aは左上の頂点の候補、Bは右下のそれである。
左上(a)を変えたときの、Bの各要素を右下にした長方形内の点の個数の変化を考える。
集合Bの各要素は自分より左上にある点たちが、現在のaより右下にあるかどうかを知りたい。
aの変化によって 右下でなくなった点、新たに右下になった点についてだけ考えればよく、集合Aを昇順(降順)に遷移すればそのような点は合計でO(N)個になる。
このような点を左上に持つようなBの要素の値を+1または-1したい。
Bが単調増加なので、これが一つの区間になる。
左端、右端を二分探索で求めて、区間加算、区間maxをRAQ&RMQで行えばO(NlogN)の計算で問題が解ける。
