ABC 401-500/ABC452F - Interval Inversion Count - 競技プログラミング用 知識集積所

---

問題

ABC452F

必要知識

B以下レベルの内容は省略

• 転倒数※
  • Fenwick木※
• 尺取法

考え方

転倒数※を求めるには、Fenwick木※を用いる方法とマージソート※を用いる方法がある。
後者はデータを使いまわしにくいので、今回は前者を用いることにする。

区間の終点を固定して始点を変化させると、区間内の転倒数は単調減少する。
ということは、転倒数がk「以下」の個数であれば、尺取法を用いて求められる。

ということは、以上を関数として切り出して2回動かし、「k個以下の個数」から「k-1個以下の個数」を引いて答えればよい。
ただし、k=0という入力の場合に「転倒数-1以下」という引数が発生することに注意。

解答例

解答例

注意点

long long型を用いる。

k=0でソート済の配列を渡された場合、全ての区間が条件を満たす。
この場合、答えがほぼ(1/2)N^2になり、int型に収まらない。

別解