みんなのプロコン D - 工場
segment treeがこういう使い方も出来る、という勉強になりました。
問題概要
毎日工場で製品をK個生産します。最初製品の在庫は無いものとして、以下の2種類のクエリが与えられるので、それを処理してください。
(1,d,a)の形式で与えられ、d日目の生産が終了したのち、製品をa個まで任意の数売る。
(2,d)の形式で与えられ、d日目までに製品を何個売れるか出力する。
解説
製品は売るときに売れるだけ売るので、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でも実装できたのかなとか思っていたりします。
