読者です 読者をやめる 読者になる 読者になる

みんなのプロコン D - 工場

segment treeがこういう使い方も出来る、という勉強になりました。

問題概要

毎日工場で製品をK個生産します。最初製品の在庫は無いものとして、以下の2種類のクエリが与えられるので、それを処理してください。

  • (1,d,a)の形式で与えられ、d日目の生産が終了したのち、製品をa個まで任意の数売る。

  • (2,d)の形式で与えられ、d日目までに製品を何個売れるか出力する。

D: 工場 - 「みんなのプロコン」 | AtCoder

解説

製品は売るときに売れるだけ売るので、d日目の生産終了時に在庫がl個でa個まで売ることが出来るとき、d日目終了時の残り在庫はmax(l-a,0)で与えられます。
よって、d日目の販売が終了したときの残り在庫の個数をl(d)個でa(d)個まで売れるとすると、
l(d)=max(l(d-1)-a(d-1),0)
という漸化式で更新できます。

しかし、d<=10^9の制限でまず間に合いません。仮にクエリを先読みして出てくる日付のみを用いて(出てこない日付は生産しか行わないことが分かるので、日付の差×kでその期間の生産数が出せる)もクエリの数が10^6なので間に合いません。

ここで、segment treeを用います。これを使うには[l,m)と[m,r)の区間でのデータから[l,r)の区間のデータを作らなくてはなりません。先ほどの残り在庫の個数の漸化式を考えます。l~m日の間の生産量から売る個数を引いた値をaと置き、在庫がx個→y個になったとすると、関数のようにy=max(x+a,b)で示せます。
同様に[m,r)の区間ではy=max(x+c,d)、[l,r)の区間でy=max(x+e,f)とすると、[l,r)の区間の関数は[l,m)の結果を[m,r)に使った合成関数と考えることが出来ます。
max(x+e,f)=max(max(x+a,b)+c,d)    xを含む式とxを含まない式に分けて、
max(x+e,f)=max(x+a+c,max(b+c,d))
e=a+c、f=max(b+c,d)
という感じで区間の統合が出来ました。

クエリ1に対しては普通のsegment treeと同様に上に向かって更新していき、クエリ2に対しては、上のxにあたる部分を左側から順に処理していけばいいです。

実際に全部の日付を配列にするとMLEするので、座標圧縮のように必要な日付のみを用いると、2種類のクエリの両方がO(nlogn)で処理できるので、時間内に処理することが出来ます。

Submission #1152510 - 「みんなのプロコン」 | AtCoder

感想

初見の時はBITで解けないか思考して駄目でした。segment treeは今まで最大値などにしか使ったことが無かったので、勉強になりました。クエリ2の部分がビットを上から見ていく操作そのものなので、かなり上手くやればBITでも実装できたのかなとか思っていたりします。