はじめに

この記事では、数列における区間MEX（Minimum Excluded Value）の重要な性質について考察します。MEXとは、数列に含まれていない最小の非負整数を指します。特に、「極小MEX区間」と呼ばれる概念に焦点を当て、その数がO(n)に収まることを証明し、効率的なアルゴリズムを提案します。

極小MEX区間の定義と重要性

極小MEX区間とは、区間の左端または右端を1つ削除するとMEX値が変化する区間のことです。この性質は、数列の区間MEX情報を効率的に管理するための基礎となります。

すべての区間[l,r]を座標(l,r)として平面直角座標系上にプロットすると、極小MEX区間の座標からO(n)個の矩形を構築できます。これにより、任意の部分区間のMEX関連情報を高速にクエリできるようになります。

極小MEX区間がO(n)個であることの証明

極小MEX区間がO(n)個しか存在しないことを証明します。まず、極小MEX区間を2つのグループに分類します：

• グループ1: a_l < a_r を満たす区間
• グループ2: a_l > a_r を満たす区間

ここで、a_l = a_r の場合、その区間は極小MEX区間ではないことに注意してください。

グループ1に着目し、各右端点rに対して対応する左端点lが一意であることを示します。仮にl' < l ≤ rなるl'が存在すると、mex(l',r) ≥ mex(l,r)となります。グループ1の定義よりa_l' < a_rであり、a_l'がMEXを増加させないため、[l',r]は極小MEX区間ではありません。

右端点の数はn個しかないため、グループ1の区間数はn以下です。同様にグループ2の区間数もn以下です。したがって、極小MEX区間の総数は2n以下、すなわちO(n)個であることが証明されました。

アルゴリズムの実装

極小MEX区間を効率的に求めるためのアルゴリズムを実装します。まず、永続セグメント木を用いて区間MEXを高速に計算できるようにします。

namespace PersistentSegmentTree {
    struct Node {
        int left, right;
        int min_val;
    } tree[MAX_NODES * 60];
    
    int create_node(int x) {
        static int idx = 0;
        ++idx;
        tree[idx] = tree[x];
        return idx;
    }
    
    void update(int& x, int l, int r, int pos, int val) {
        x = create_node(x);
        if (l == r) {
            tree[x].min_val = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            update(tree[x].left, l, mid, pos, val);
        } else {
            update(tree[x].right, mid + 1, r, pos, val);
        }
        tree[x].min_val = min(tree[tree[x].left].min_val, tree[tree[x].right].min_val);
    }
    
    int query(int x, int l, int r, int threshold) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (tree[tree[x].left].min_val < threshold) {
            return query(tree[x].left, l, mid, threshold);
        } else {
            return query(tree[x].right, mid + 1, r, threshold);
        }
    }
    
    struct SegmentTree {
        int root;
        struct Iterator {
            int pos;
            SegmentTree* tree;
            void operator=(int v) {
                update(tree->root, 0, MAX_N + 1, pos, v);
            }
            operator int() {
                return query(tree->root, 0, MAX_N + 1, pos);
            }
        };
        Iterator operator[](int p) {
            return {p, this};
        }
    };
}

MEX値0と1の区間を事前に処理します。次に、極小MEX区間の特徴を活かして構築します。区間[l,r]のMEXがvである極小区間について、lより小さい最初の位置Lとrより大きい最初の位置Rを見つけます。

vector> mex_intervals[MAX_VALUES];

namespace MexCalculator {
    vector<int> positions[MAX_VALUES];
    PersistentSegmentTree::SegmentTree seg_trees[MAX_VALUES];
    
    int compute_mex(int l, int r) {
        return seg_trees[r][l];
    }
    
    int find_prev(int pos, int val) {
        auto it = lower_bound(positions[val].begin(), positions[val].end(), pos);
        if (it == positions[val].begin()) return -1;
        return *(--it);
    }
    
    int find_next(int pos, int val) {
        auto it = upper_bound(positions[val].begin(), positions[val].end(), pos);
        if (it == positions[val].end()) return -1;
        return *it;
    }
    
    void process_mex_intervals(int v) {
        sort(mex_intervals[v].begin(), mex_intervals[v].end());
        vector> filtered;
        for (auto [l, r] : mex_intervals[v]) {
            while (!filtered.empty() && r <= filtered.back().second) {
                filtered.pop_back();
            }
            filtered.push_back({l, r});
        }
        mex_intervals[v] = filtered;
        
        for (auto [l, r] : mex_intervals[v]) {
            const int L = find_prev(l, v);
            const int R = find_next(r, v);
            if (L != -1) {
                mex_intervals[compute_mex(L, r)].push_back({L, r});
            }
            if (R != -1) {
                mex_intervals[compute_mex(l, R)].push_back({l, R});
            }
        }
    }
    
    void solve() {
        for (int i = 1; i <= n; i++) {
            seg_trees[i] = seg_trees[i - 1];
            seg_trees[i][array[i]] = i;
            positions[array[i]].push_back(i);
            
            if (array[i] != 0) {
                mex_intervals[0].push_back({i, i});
            } else {
                mex_intervals[1].push_back({i, i});
            }
        }
        
        for (int i = 1; i <= n + 1; i++) {
            process_mex_intervals(i);
        }
    }
}

アルゴリズムの分析

このアルゴリズムの時間計算量はO(n log n)です。セグメント木の更新とクエリはO(log n)時間かかり、各MEX値について区間を処理する部分もO(n log n)時間で完了します。空間計算量はO(n log n)です。

このアルゴリズムを用いることで、数列のすべての極小MEX区間を効率的に列挙できます。これにより、数列の区間MEXに関する問題を高速に解決することが可能になります。