二次元BIT
一点加算を含む、長方形領域内部の総和取得クエリに答えていく!動的二次元 BIT や、BIT on Wavelet Matrix などで通せる。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個のクエリに答えよ。 クエリタ…
色んな解法があると思う。動的二次元 BIT や Wavelet Matrix など。ここでは、BIT on Wavelet Matrix (加算クエリはないのでやや過剰) で通してみた。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個の…
BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…
Wavelet Matrix の練習に 問題へのリンク 問題概要 初期状態が の順列である数列 が与えられる。 次の 2 種類のクエリに答えよ。なお、 番目 () のクエリをこなした後には、数列は 個に分割された状態となる。 クエリタイプ 1:群数列の 番目について、先頭…
領域加算、領域和取得の両方に対応した二次元 BIT ライブラリを目指した 問題概要 N × N の盤面において以下の M 個のクエリに答えよ: 長方形領域 [x0, y0] × [x1, y1] の XOR 和を出力 長方形領域 [x0, y0] × [x1, y1] 全体に一様に値 v を XOR 加算 考えた…
二次元 BIT ライブラリ の verify をした 問題へのリンク 問題概要 H × W のプレートにたこ焼きを置いて焼いていく。配置されたたこ焼きは「焼き上がった」「まだ焼き上がっていない」の 2 つの状態を持つ。なお、たこ焼きは配置されてから焼き上がるまでの…