ユニークビジョンプログラミングコンテスト2022 冬 (AtCoder Beginner Contest 283) F - Permutation Distance (500)
解説の解法
求めたい式を変形すると$ (i,j), (p_i,p_j)の大小毎の4パターンの最小値にすることができる
端から順にセグ木に値を入れて求めていくと一個あたり$ \mathcal{O}(N \log N)で求まる
どれか一つの式を他に使い回すことができる
$ p[i] = n + 1 - p[i] するとminとmax、AとB、式の順序が入れ替わる
$ d,pを反転すると、$ (i,j)の向き、AとBが入れ替わる
問題: https://atcoder.jp/contests/abc283/tasks/abc283_f
提出: https://atcoder.jp/contests/abc283/submissions/39774510
#ユニークビジョンプログラミングコンテスト2022冬 #ユニークビジョンプログラミングコンテスト #ABC283 #500pt #F #ABC #AtCoder
#場合分け