Codeforces Round #176 (Div. 1) D. Tourists

JOIerお家芸感。なんかこれはJOIerは結構見た瞬間簡単だなあと思う気がする。おそらくDではない。

 

原点にある点がn個あり、i個目の点は時刻q[i]に原点を出発し、x軸の正方向に沿って速さ1で進む。また、それとは別にm個の線分が存在して、i番目の線分は時刻t[i]に区間[l[i], r[i]]を覆うように一瞬の内に出現する。各点について、点が線分に覆われながら移動している時間の長さを求めよ。

 

なんか本当に簡単で、div1Dにしては簡単だと思うんだけど、1つの線分(l, r, t)に注目した時、q[i] >= t-lであるような点iはその線分によって、r-l秒覆われていることになる。そして、これはどう見てもqに関して単調性がある、すなわち、q[j] >= q[i] >= t-lであれば、点jもr-l秒覆われることになるから、点をq[i]で昇順にsortしておけば、二分探索により、r-l秒覆われる点が全て分かる上、imos法を用いれば、全ての線分について考えたときの具体的な秒数の合計も一瞬で分かる。ここで少し怖くなるのは、t-r+1 <= q[i] < t-lであるような点iについては、点が移動している途中で線分が出現するので、具体的には、q[i]+r-t秒だけ微妙に覆われることになる。しかしこれも同様に二分探索とimos法によって対応可能で、どうするかというと、二分探索でt-r+1 <= q[i] < t-lを満たすiの範囲を求めた上で、定数r-tを普通のimos法で計算(A[i]にi番目の点のこの定数に関する累積和が入るとする)、定数1をimos法で計算する(P[i]にこの累積和が入るとする)と、微妙に覆われた時間の累計はP[i]*q[i] + A[i]で求まる。1次関数の累積を求めているイメージ。基本的にはこれだけなんだけど、後は線分に重複があるところだけ解決しないといけない。これは、各座標において、その座標を覆う線分の内、tが最小であるものを求めればよい。これは結構明らかだと思う(tが最小であるような線分以外を無視すれば重複は解決され、かつ最も覆われる点が多い)。実際に各座標についてやると当然計算量がやばいが、これは簡単なイベント走査で解決できる。線分(l, r, t)についてイベント(l, t)とイベント(r, t)を作成し、イベントの集合を1つ目の要素に関してソート。multisetを1つ使って(l, t)が来たらtをinsert、(r, t)が来たらtをeraseしていけば、連続する2つのイベント(x1, t1), (x2, t2)について、区間[x1, x2]におけるtの最小値は、イベント(x1, t1)を処理し終わった後のmultisetの最小値となる。これも多分典型。なので各イベントの処理後に新しい線分の集合に、それらの値を追加してやれば、重複を取り除いた線分が全て求められて、解ける。このやり方ではどうやっても、重複を取り除いた線分は流石に自明にO(m)個しか存在しないので、かなり適当に追加しても問題ない。

 

ちなみに初め誤読して、「点は線分に覆われなくなったらその場で止まる。」という条件があると思っていたんだけど、それでも解けるので考えてみてください。