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

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

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

ウェーブレット行列

line

  • AIZU ONLINE JUDGE

    • 問題
      • N(<=105)個の豆があり,それぞれの硬さが与えられる.次のQ(<=105)個のクエリに答えよ.
        • 区間[l,r]の豆の中で硬さDに最も近い豆の硬さとの差の絶対値を求めよ.
    • 必要な操作
      • prevValue, nextValue
  • 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

  • Treasure Hunt | Aizu Online Judge

    • 問題
      • N(<=5000)個のお宝があり,それぞれ位置y(<=109)とx(<=109)が与えられる.次のQ(<=5 * 105)個のクエリに答えよ.
        • 領域[x1, y1, x2, y2]に含まれるお宝の数を求める.
    • 必要な操作
      • freqRange
    • ソース
    • 解法
      • ウェーブレット行列で二次元データを扱う方法はウェーブレット木の世界に詳しいです.この方法ではxの値がすべて異なっている必要があるので,各点に番号を振り直すことでx,yともに同じ値がでないようにします.
  • D - Axis-Parallel Rectangle

    • 問題
      • N(<=50)個の点があり,それぞれ位置y(-109 <= y <= 109)とx(-109 <= x <= 109)が与えられる.内部にK個以上の点を含むような最小の長方形の面積を求めよ.
    • 必要な操作
      • freqRange
    • ソース
    • 上とほとんど同じです.ウェーブレット行列では負の値が扱えないので,座標圧縮をして正の値に修正する必要があります.

動的ウェーブレット行列

ilne

参考