ウェーブレット行列で競プロの問題を解く

ウェーブレット行列を使う練習

ウェーブレット行列についてはウェーブレット行列を参照してください.
動的ウェーブレット行列については動的ウェーブレット行列を参照してください.

ウェーブレット行列

line

  • Hard Beans

  • No.738 平らな農地 - yukicoder

    • 問題
      • N(<=105)個の整数がある.Aの任意の要素をaからbにするためには|a - b|のコストがかかる.K個以上の連続した区間の要素の値を同じにするための最小コストを求めよ.
    • 必要な操作
      • quantileRange, rangeSum, rangeFreq
    • ソース
    • 解法
      • 変更後の値はその区間の中央値Mを選べばいいです.これはquantileRangeで求めることができます.
      • 変更するコストは,Mより小さい要素と大きい要素にわけて考えます.小さい要素の変更コストは「M * Mより小さい要素の頻度 - Mより小さい要素の合計」で求めることができます.大きいものも同様です.この合計がコストとなります.頻度はrangeFreq,合計はrangeSumで求めることができます.ただし,rangeSumはtopKを使ったものだとTLEになってしまうので,事前にウェーブレット行列の索引の行ごとに累積和をとって計算量を削減する必要があります.
  • Problem - D - Codeforces

    • 問題
      • N(<=105)個の整数と整数T(<=2 * 1014)が与えられる.区間[l, r]の要素の合計がTより小さくなるような(l, r)のペアの個数を求めよ.
    • 必要な操作
      • rangeFreq
    • ソース
    • 解法
      • はじめに累積和csをとっておきます.cs[r] - cs[l] <Tとなるようなlの個数をカウントすればいいです.式変形するとcs[r] - Tより大きいようなcs[l]を探すことになります.これはrangeFreqで求めることができます.ただし累積和に負の値がでることがあるので,累積和ででてきた最小の値を引くことですべて正の整数になるようにする必要があります(ウェーブレット行列は負の値が扱えないので).またTを引くことで負になることもあるので,Tが正の場合はTを足して調節しておきます.

grid

動的ウェーブレット行列

ilne

参考