【問題集】二次元累積和
AOJ
WaveletMatrix
クエリ:長方形区間
二次元平面上のN点の問題
クエリ処理問題
動的二次元セグメント木(BIT含む)
座標圧縮
二次元累積和
累積和
【問題集】二次元累積和
BIT
二次元BIT
動的セグメント木(BIT含む)
区間に含まれる点の重みの最大値を求める
BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…
AtCoder
ABC-E
水色diff
二次元グリッド
グリッド上のDP
DP
二次元累積和
累積和
二分探索
【問題集】累積和・二分探索法・しゃくとり法
典型要素を詰め合わせた教育的問題
0と1の問題
制約条件:正方形領域
数え上げ問題
解空間:O(N^2)通りの選択肢
極大なものを考える
sparseな問題
ある量を固定して考える
そのまま覚えたい典型問題
単調性に着目する
累積和テク:区間の総和を累積和で高速に求める
【問題集】累積和
【問題集】二次元累積和
【問題集】累積和・いもす法
AtCoder475点
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
二次元累積和!! ジャッジページ 問題文 問題概要 のグリッドが与えられる。各マスには整数値 が描かれている。整数値は 以上 以下である。 これらのグリッド中の の長方形領域であって、その内部に -1 を含まないものを考える。そのような長方形領域に含ま…
AtCoder
旧ARC-B
水色diff
二次元累積和
累積和
二次元グリッド
制約条件:各グループの何かが等しい
典型要素を詰め合わせた教育的問題
【問題集】累積和
【問題集】二次元累積和
【問題集】累積和・二分探索法・しゃくとり法
区間の長さの最大値または最小値を求める
区間
制約条件:長方形領域
累積和テク:区間の総和を累積和で高速に求める
【問題集】累積和・いもす法
二次元累積和のいい感じの練習問題!! ただこれ水色って......現代なら、茶色くらいに感じる。 問題へのリンク 問題概要 市松模様に塗られた のマス目があって、各マスには整数値が書かれている。以下の条件を満たす長方形領域の面積の最大値を求めよ。 そ…