問題：A - 長いだけのネクタイ (Just Long Neckties)
解答：Submission #19055773 - JOI 2019/2020 本選 過去問
解法：試着会のネクタイ(a)を除いた後に奇妙さを調べる際は、試着会のネクタイ・社員のネクタイ(b)どちらも昇順ソートしてmax(a - b, 0)を調べるのが最適。理由は、ソート後の状態からi, jを選んでa[i], a[j]とb[i], b[j]それぞれをスワップしても奇妙さが減ることはないため。
試着会のネクタイを除く前にソートしておく。試着会のネクタイを除いた後、除いたネクタイよりソート順が前のネクタイとソート順が後のネクタイとでbと対応する添字が1つずれることになる。逆に言うとこの部分のみが変わるため、前計算によってmaxを取る作業を高速化できる。すなわち、除いたネクタイよりソート順が前のネクタイの奇妙さの最大値を求めるための左からの累積maxと、除いたネクタイよりソート順が後のネクタイの奇妙さの最大値を求めるための右からの累積maxを前計算しておけばよい。
