「No.647 明太子 」 を無駄にセグ木を使って早くする解説
タイトル名が雑でごめんなさい。 解説の書き方が良くわかりません。(今まで参加記しか書いてこなかった)
問題: No.647 明太子 - yukicoder
僕の愚直解法: #234780 No.647 明太子 - yukicoder
僕のセグ木解法: #235796 No.647 明太子 - yukicoder
想定解は,O(NM)ですが、セグ木を用いるとO( (n+m) log(n+m) )になります。 まず、入力を受け取って、辛さを座圧します。 そして、人と明太子を並べて、値段(と予算)が高い順にソートします。 このとき、それがおなじなら人のほうが先に来るようにします。(同額ならば買うため) そして、辛さを†セグ木†で持ちます。(BITでもいけるけど、ぼくはBITの使い方がわかりません) すると、人が来た時に、要求する辛さを持っておいて、明太子が来た時に、それ以下の辛さを要求する人の人数がその明太子の購入される数になります。 よって、座圧とセグ木に必要な、O( (n+m)log(n+m) )で解けます。 ちなみに、もとの制約が小さい&いろいろさぼったので、愚直と比べて2倍しか早くなりませんでした。 最速コードはほかの人がBITをつかっていました。(僕はbit演算が苦手なのでセグ木を使い、2倍遅い)
