ウェーブレット行列を使う練習
ウェーブレット行列についてはウェーブレット行列を参照してください.
動的ウェーブレット行列については動的ウェーブレット行列を参照してください.
ウェーブレット行列
line
-
- 問題
- N(<=105)個の豆があり,それぞれの硬さが与えられる.次のQ(<=105)個のクエリに答えよ.
- 区間[l,r]の豆の中で硬さDに最も近い豆の硬さとの差の絶対値を求めよ.
- N(<=105)個の豆があり,それぞれの硬さが与えられる.次のQ(<=105)個のクエリに答えよ.
- 必要な操作
- prevValue, nextValue
- ソース
- 問題
-
- 問題
- N(<=105)個の整数がある.Aの任意の要素をaからbにするためには|a - b|のコストがかかる.K個以上の連続した区間の要素の値を同じにするための最小コストを求めよ.
- 必要な操作
- quantileRange, rangeSum, rangeFreq
- ソース
- 解法
- 変更後の値はその区間の中央値Mを選べばいいです.これはquantileRangeで求めることができます.
- 変更するコストは,Mより小さい要素と大きい要素にわけて考えます.小さい要素の変更コストは「M * Mより小さい要素の頻度 - Mより小さい要素の合計」で求めることができます.大きいものも同様です.この合計がコストとなります.頻度はrangeFreq,合計はrangeSumで求めることができます.ただし,rangeSumはtopKを使ったものだとTLEになってしまうので,事前にウェーブレット行列の索引の行ごとに累積和をとって計算量を削減する必要があります.
- 問題
-
- 問題
- 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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426
- 問題
- N(<=5000)個のお宝があり,それぞれ位置y(<=109)とx(<=109)が与えられる.次のQ(<=5 * 105)個のクエリに答えよ.
- 領域[x1, y1, x2, y2]に含まれるお宝の数を求める.
- N(<=5000)個のお宝があり,それぞれ位置y(<=109)とx(<=109)が与えられる.次のQ(<=5 * 105)個のクエリに答えよ.
- 必要な操作
- freqRange
- ソース
- 解法
- ウェーブレット行列で二次元データを扱う方法はウェーブレット木の世界に詳しいです.この方法ではxの値がすべて異なっている必要があるので,各点に番号を振り直すことでx,yともに同じ値がでないようにします.
- 問題
-
- 問題
- N(<=50)個の点があり,それぞれ位置y(-109 <= y <= 109)とx(-109 <= x <= 109)が与えられる.内部にK個以上の点を含むような最小の長方形の面積を求めよ.
- 必要な操作
- freqRange
- ソース
- 上とほとんど同じです.ウェーブレット行列では負の値が扱えないので,座標圧縮をして正の値に修正する必要があります.
- 問題
動的ウェーブレット行列
ilne
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A&lang=jp
- 問題
- N(<=105)個の要素をもつ配列Aがある.要素ははじめすべて231 - 1である.次のQ(<=105)個のクエリに答えよ.
- i番目の要素をxに変更する.
- 区間[s, t]の最小値を求める.
- N(<=105)個の要素をもつ配列Aがある.要素ははじめすべて231 - 1である.次のQ(<=105)個のクエリに答えよ.
- 必要な操作
- update, minRange
- ソース
- 解法
- 貼るだけ
- 問題
-
- 問題
- N(<=104) 個の本棚があり,各本棚にはA_i冊の本が入っている.次のQ(<=104)個のクエリに答えよ.
- x番目の本棚の本の数をkにする.
- x番目からy番目の本棚のうち,本の数が少ない方から見てk番目の本棚に入っている本の数を求める.
- N(<=104) 個の本棚があり,各本棚にはA_i冊の本が入っている.次のQ(<=104)個のクエリに答えよ.
- 必要な操作
- update, quantile
- ソース
- 解法
- 貼るだけ
- 問題
-
- 問題
- 必要な操作
- erase, insert, rank
- ソース
- 解法
- 貼るだけ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508
- 問題
- 必要な操作
- erase, insert, rangemin
- ソース
- 解法
- 貼るだけ
-
- 問題
- 空の配列がある.次のQ(<=105)個のクエリに答えよ.
- 数値zを配列の最後尾につける
- x番目の要素を削除する
- x番目の要素を数値zにする
- 区間[L, R]のk番目に小さい値を求める
- 空の配列がある.次のQ(<=105)個のクエリに答えよ.
- 必要な操作
- erase, insert, quantileRange
- ソース
- 解法
- 貼るだけ
- 問題
-
- 問題
- 空の集合Sがある.次のQ(<=2*105)個のクエリに答えよ.
- Sに数Xを追加する
- Sに含まれる数のうちX番目に小さい数を答え,その数をSから削除する
- 空の集合Sがある.次のQ(<=2*105)個のクエリに答えよ.
- 必要な操作
- erase, insert, quantileRange
- ソース
- 解法
- 動的ウェーブレット行列だとTLEだったけど動的ウェーブレット木だと通りました.
- 問題