PAST1H

from 第一回 アルゴリズム実技検定 PAST1H H - まとめ売り

• 考えたこと
  • 20万種類の商品を20万回売る
  • 在庫チェックのコストを下げたい
    • クエリ2,3の成功した販売数a,bを持つ
      • まとめて売った時の残り在庫数はこの値を更新する
    • クエリ2,3の範囲の最小値を前計算しておく
      • クエリ2,3ができるかはこの値を見る
    • クエリ1の時は奇数番目ならx-a-b、違えばx-aが残り在庫
• 公式解説OK