ABC467 F - Email Scheduling Optimization

考え方

まず、クエリを無視して、最初のデータでの最善の値を考える。
これは単純な貪欲法でよく、$B$ の値が大きいものから順にメールを書いて送ればよい。
全てのメールのうち、「そのメールを書き終わる時刻+返信にかかる時間」の最大値が答え。

さて、ではクエリで情報が書き換わる場合はどうか。
まず、上記の話をsegment木に持たせることにする。
segment木のデータは「すべてのメールを書き終えるまでの時間、すべての返信が届くまでの時間」。
単位元は $\{0,0\}$ である。
$B$ の値が大きい順に並べてあれば、データの結合は簡単。

こうすると、$A$ の値の更新は簡単。
$B$ の大きさが変わらないのだから、セグ木の $1$ ヶ所を書き換えるだけでよい。

問題は $B$ の更新。
この場合はsegment木上の順序を変えなければならない。
そこで事前にクエリの内容を全て確認し、セグ木上の移動予定地点に単位元を置いておく。
何番目のクエリでsegment木上の何番目に移動するのかも事前に調べておく。
そうすれば、segment木上の順序変えが実現できる。

以上でこの問題が解け、あとはここから先の実装を頑張るだけ。
計算量は、$O((N+Q)\log (N+Q))$。

入力例1での動作

入力を受け取る。

n: 3
q: 3
a: {4, 6, 7}
b: {4, 6, 7}

1 2 1
2 3 7
2 3 1

タイプ $2$ のクエリで現れる変更後の $B$ も含め、
$B$ の大きい順に使う位置をあらかじめ確保する。

初期状態では、位置 $1,2,3$ に会社 $3,2,1$ の情報が入る。
各会社の葉の値は $\{A,A+B\}$ である。

位置0: e
位置1: {7, 14}
位置2: {6, 12}
位置3: {4, 8}
位置4: e

全体を結合すると {17, 21} となる。

$1$ つめのクエリは 1 2 1 である。
会社 $2$ の $A$ が $6$ から $1$ に変わる。

$B$ は $6$ のままなので位置 $2$ から動かず、
その場所の値だけ {1, 7} に変える。

位置0: e
位置1: {7, 14}
位置2: {1, 7}
位置3: {4, 8}
位置4: e

メールを書く順は会社 $3,2,1$ である。
書き終わる時刻は順に $7,8,12$、
返信が届く時刻は $14,14,16$ となる。

よって、$1$ つめの答えは $16$ である。

$2$ つめのクエリは 2 3 7 である。
会社 $3$ の $B$ は元から $7$ だが、
コードではこのクエリ用に確保した位置 $0$ へ移動する。

位置0: {7, 14}
位置1: e
位置2: {1, 7}
位置3: {4, 8}
位置4: e

順序としては変わらないので、答えは再び $16$ である。

$3$ つめのクエリは 2 3 1 である。
会社 $3$ の $B$ が $7$ から $1$ に変わるので、
位置 $0$ から位置 $4$ へ移動する。

位置0: e
位置1: e
位置2: {1, 7}
位置3: {4, 8}
位置4: {7, 8}

今度の順序は会社 $2,1,3$ である。
書き終わる時刻は順に $1,5,12$、
返信が届く時刻は $7,9,13$ となる。

したがって、$3$ つめの答えは $13$ である。

以上より、各クエリの答えは順に $16,16,13$ となる。

注意点

答えは、int 型からはみ出る。
segment木で管理する値と答えには、long long 型を用いること。

別解

特になし。