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での動作

入力を受け取る。

クエリ内の宛先番号は、入力時に $1$ ずつ減らして 0-indexed に直す。

n: 3
q: 3
a: {4, 6, 7}
b: {4, 6, 7}
type: {1, 2, 2}
p: {1, 2, 2}
x: {1, 7, 1}

初期状態の b と、タイプ $2$ のクエリで現れる変更後の b を tmp に入れる。

各要素の second には、初期状態なら宛先番号、クエリなら n とクエリ番号の和を入れる。

tmp を降順にソートする。

tmp: {(7,4), (7,2), (6,1), (4,0), (1,5)}

セグ木上の位置を pos に記録する。

pos: {3, 2, 1, -1, 0, 4}

サイズ $5$ のsegment木を用意する。

初期状態の各会社のデータを、pos が示す位置に入れる。

$1$ つめのクエリは 1 2 1 である。

p[0]=1 なので、a[1] を $1$ に変更する。

b[1] は変化しないので、セグ木上の位置は変更しない。

a: {4, 1, 7}
b: {4, 6, 7}

位置 2 の値を {1,7} に変更する。

all_prod() の second である $16$ が答え。

result: {16, 0, 0}

$2$ つめのクエリは 2 3 7 である。

p[1]=2 なので、b[2] を $7$ に変更する。

元から b[2]=7 だが、コードでは、このクエリ用に確保した位置へデータを移動する。

元の位置 1 を単位元に戻し、pos[4]=0 へ移動する。

a: {4, 1, 7}
b: {4, 6, 7}
pos[2]: 0

all_prod() の second である $16$ が答え。

result: {16, 16, 0}

$3$ つめのクエリは 2 3 1 である。

p[2]=2 なので、b[2] を $1$ に変更する。

元の位置 0 を単位元に戻し、pos[5]=4 へ移動する。

a: {4, 1, 7}
b: {4, 6, 1}
pos[2]: 4

all_prod() の second である $13$ が答え。

result: {16, 16, 13}

注意点

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

別解

特になし。