けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

二次元BIT

Yosupo Library Checker - Point Add Rectangle Sum

一点加算を含む、長方形領域内部の総和取得クエリに答えていく!動的二次元 BIT や、BIT on Wavelet Matrix などで通せる。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個のクエリに答えよ。 クエリタ…

Yosupo Library Checker - Rectangle Sum

色んな解法があると思う。動的二次元 BIT や Wavelet Matrix など。ここでは、BIT on Wavelet Matrix (加算クエリはないのでやや過剰) で通してみた。 問題へのリンク 問題概要 二次元平面上に 点ある。 番目の点の座標は であり、重みは である。次の 個の…

AOJ 2426 Treasure Hunt

BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…

AtCoder ABC 324 G - Generate Arrays (橙色, 600 点)

Wavelet Matrix の練習に 問題へのリンク 問題概要 初期状態が の順列である数列 が与えられる。 次の 2 種類のクエリに答えよ。なお、 番目 () のクエリをこなした後には、数列は 個に分割された状態となる。 クエリタイプ 1:群数列の 番目について、先頭…

Codeforces Round #198 (Div. 1) D - Iahub and Xors (R2500)

領域加算、領域和取得の両方に対応した二次元 BIT ライブラリを目指した 問題概要 N × N の盤面において以下の M 個のクエリに答えよ: 長方形領域 [x0, y0] × [x1, y1] の XOR 和を出力 長方形領域 [x0, y0] × [x1, y1] 全体に一様に値 v を XOR 加算 考えた…

AOJ 2842 たい焼きマスターと食べ盛り

二次元 BIT ライブラリ の verify をした 問題へのリンク 問題概要 H × W のプレートにたこ焼きを置いて焼いていく。配置されたたこ焼きは「焼き上がった」「まだ焼き上がっていない」の 2 つの状態を持つ。なお、たこ焼きは配置されてから焼き上がるまでの…