クエリ:長方形区間
YosupoLibraryChecker
WaveletMatrix
BIT
二次元BIT
動的セグメント木(BIT含む)
動的二次元セグメント木(BIT含む)
クエリ処理問題
クエリ:長方形区間
区間に含まれる点の重みの最大値を求める
一点加算を含む、長方形領域内部の総和取得クエリに答えていく!動的二次元 BIT や、BIT on Wavelet Matrix などで通せる。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個のクエリに答えよ。 クエリタ…
YosupoLibraryChecker
クエリ処理問題
WaveletMatrix
BIT
二次元BIT
動的セグメント木(BIT含む)
動的二次元セグメント木(BIT含む)
クエリ:長方形区間
二次元平面上のN点の問題
区間に含まれる点の重みの最大値を求める
色んな解法があると思う。動的二次元 BIT や Wavelet Matrix など。ここでは、BIT on Wavelet Matrix (加算クエリはないのでやや過剰) で通してみた。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個の…
AOJ
WaveletMatrix
クエリ:長方形区間
二次元平面上のN点の問題
クエリ処理問題
動的二次元セグメント木(BIT含む)
座標圧縮
二次元累積和
累積和
【問題集】二次元累積和
BIT
二次元BIT
動的セグメント木(BIT含む)
区間に含まれる点の重みの最大値を求める
BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…