区間MEXの重要な性質とそのアルゴリズム
はじめに
この記事では、数列における区間MEX（Minimum Excluded Value）の重要な性質について考察します。MEXとは、数列に含まれていない最小の非負整数を指します。特に、「極小MEX区間」と呼ばれる概念に焦点を当て、その数がO(n)に収まることを証明し、効率的なアルゴリズムを提案します。
極小MEX区間の定義と重要性
極小MEX区間とは、区間の左端または右端を1つ削除 ...
7月15日 22:49 投稿
線分木を使用した複雑な操作の実装
この問題では以下の4つの操作を実装する必要があります：
操作1: 結果にaを加算
操作2: 結果からaを減算
操作3: 結果にaを乗算
操作4: 結果にa * Xを加算
これらの操作を効率的に処理するために、線分木を使用します。線分木は区間最大値と最小値、加算の遅延評価タグ、乗算の遅延評価タグ、代入の遅延評価タグ、および操作4用の遅延評価タグを管理します。
木の構築
通 ...
6月12日 18:13 投稿
高度なアルゴリズム - バイナリインデックストリーとセグメントツリー
バイナリインデックストリー
単点更新、範囲照会が可能なデータ構造です。
典型的な問題として、数列の特定の位置を更新し、任意の区間の合計を求める操作が考えられます。
このデータ構造の核となるのがlowbit関数です。これは整数xに対して、xの最も右側にある1を含む部分を返す操作です。具体的にはx&-xと表現できます。
実装の基本となるのはtree配列です。各要素t ...
6月10日 23:11 投稿