遅延評価セグメント木の練習！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ()：数列の区間 内の要素の総和を 99824435…

遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…

遅延評価セグメント木の練習問題！ 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列 が与えられる。次の 2 種類のクエリに答えよ。 クエリ (1 L R)：文字列 の区間 内における、1 が連続する区間の長さの最大値を答えよ クエリ (2 L R)：文字列 …

「区間値更新」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x)： を に変更する クエリタイプ (1 s t)： の総和…

「区間加算」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x)： に を加算する クエリタイプ (1 s t)： の総和を…

Starry Sky Tree は「区間 加算」「区間最小値取得」を処理する遅延セグ木だった。 今回は「区間 更新」「区間最小値取得」を処理する遅延セグ木を実装する。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は…

この問題は、人生で最初に挑む遅延セグ木の問題としてオススメ！Starry Sky Tree と呼ばれるものでもある。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s…

まさに遅延評価セグメント木の練習問題！！！ 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…

遅延評価セグメントツリーで殴った...速度重視ならそれでいい気もする 問題へのリンク 問題概要 本の竹があって、時刻 0 においてすべての竹の高さは 0 である。それぞれの竹は時刻が 1 経過するごとに高さが 1 増える。 竹を伐採するイベントが 回予定され…

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…