区間monoid要約
queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。
この典型を扱う単元: 区間monoid要約
検索別名: monoid range query、segment tree、セグメント木、線分木
未知問からこの典型を見つける手掛かり
- 扱う対象
- monoid
- 区間
- 要約
- 使う手掛かり
- point update
- range fold
- 非可換合成
- 保つ不変量
- 単位元
- 結合法則
- 順序
- 求めるもの
- 区間query
- 境界探索
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- Euler順による部分木区間化: 部分木を連続区間へ写し、区間集約・一点更新・差分伝播へ接続するときに併用する。
学習成果と学習単位
要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
区間monoid要約で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC223 F「Parenthesis Checking」 公式問題主題: 区間monoid要約 / 主タグ
- ABC343 F「Second Largest Query」 公式問題主題: 区間monoid要約 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC223 F「Parenthesis Checking」 公式問題主題: 区間monoid要約 / 主タグ
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP / 補助タグ
技能・出典
主題: 値域集約による部分列DP
主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC246 Ex「01? Queries」 公式問題主題: 区間monoid要約 / 主タグ
- ABC248 Ex「Beautiful Subsequences」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 補助タグ
- ABC254 F「Rectangle GCD」 公式問題主題: gcd不変量・差分構造 / 補助タグ
- ABC262 F「Erase and Rotate」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC265 G「012 Inversion」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC266 Ex「Snuke Panic (2D)」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する / 補助タグ
技能・出典
主題: 接尾辞の順序とLCPを索引化する
主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC283 F「Permutation Distance」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC285 F「Substring of Sorted String」 公式問題主題: 区間monoid要約 / 主タグ
- ABC292 Ex「Rating Estimator」 公式問題主題: 区間monoid要約 / 主タグ
- ABC299 G「Minimum Permutation」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC309 F「Box in Box」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC322 F「Vacation Query」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC331 F「Palindrome Query」 公式問題主題: 区間monoid要約 / 主タグ
- ABC339 E「Smooth Subsequence」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC343 F「Second Largest Query」 公式問題主題: 区間monoid要約 / 主タグ
- ABC353 G「Merchant Takahashi」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC354 F「Useless for LIS」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC356 F「Distance Component Size Query」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
- ABC357 F「Two Sequence Queries」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC360 G「Suitable Edit for LIS」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC365 F「Takahashi on Grid」 公式問題主題: 区間monoid要約 / 主タグ
- ABC388 G「Simultaneous Kagamimochi 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC408 F「Athletic」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC415 F「Max Combo」 公式問題主題: 区間monoid要約 / 主タグ
- ABC418 F「We're teapots」 公式問題主題: 区間monoid要約 / 主タグ
- ABC424 F「Adding Chords」 公式問題主題: 区間monoid要約 / 主タグ
- ABC429 F「Shortest Path Query」 公式問題主題: 区間monoid要約 / 主タグ
- ABC432 E「Clamp」 公式問題主題: 区間monoid要約 / 主タグ
- ABC434 G「Keyboard」 公式問題主題: 区間monoid要約 / 主タグ
- ABC437 F「Manhattan Christmas Tree 2」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC440 F「Egoism」 公式問題主題: 区間monoid要約 / 主タグ
- ABC447 G「Div. 1 & Div. 2」 公式問題主題: 区間monoid要約 / 主タグ
- ABC453 G「Copy Query」 公式問題主題: 永続data structure・structural sharing / 補助タグ
技能・出典
主題: 永続data structure・structural sharing
主タグ: 永続data structure・structural sharing / 補助タグ: 区間monoid要約
- ABC460 F「Farthest Pair Query」 公式問題主題: 区間monoid要約 / 主タグ