遅延評価する区間作用
区間更新を要約へ作用させ、作用の合成を遅延評価する。
この典型を扱う単元: 区間更新を要約へ作用させる
検索別名: lazy propagation、lazy segment tree、遅延セグメント木
未知問からこの典型を見つける手掛かり
- 扱う対象
- 区間更新
- 区間要約
- 遅延値
- 使う手掛かり
- range update
- 区間代入
- 区間加算
- 保つ不変量
- lazy
- 作用
- 合成順
- 求めるもの
- 区間操作
- 更新とquery
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- 区間monoid要約: 区間要約のmonoidと、その要約へ作用する写像を基盤として遅延更新を実装する。
学習成果と学習単位
更新作用の合成順と要約への適用を定義し、遅延評価で保てる。
区間更新を要約へ作用させるで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC340 E「Mancala 2」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC382 F「Falling Bars」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC237 G「Range Sort Query」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC237 G「Range Sort Query」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC248 Ex「Beautiful Subsequences」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 補助タグ
- ABC256 Ex「I like Query Problem」 公式問題主題: 単調進行による償却解析 / 補助タグ
- ABC262 Ex「Max Limited Sequence」 公式問題主題: prefix分割DP / 補助タグ
- ABC265 G「012 Inversion」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC322 F「Vacation Query」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC327 F「Apples」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC332 F「Random Update Query」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC340 E「Mancala 2」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC346 G「Alone」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC357 F「Two Sequence Queries」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC360 F「InterSections」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC363 G「Dynamic Scheduling」 公式問題主題: rollback・DFS入退場の状態復元 / 補助タグ
技能・出典
主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 二部matching・Hall・Kőnig、遅延評価する区間作用、Segment Treeのcanonical区間分解
- ABC371 F「Takahashi in Narrow Road」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC382 F「Falling Bars」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC389 F「Rated Range」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC397 F「Variety Split Hard」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC417 F「Random Gathering」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC426 F「Clearance」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC441 G「Takoyaki and Flip」 公式問題主題: 区間更新を要約へ作用させる / 主タグ
- ABC450 F「Strongly Connected 2」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC455 F「Merge Slimes 2」 公式問題主題: 区間更新を要約へ作用させる / 主タグ