StaticRangeMexQuery
コードについての説明
更新のない状況で区間 mex クエリ ${\mathrm{mex}} \{ a_l, ..., a_{r-1} \}$ を効率的に処理するデータ構造.
集合 $S$ の $\mathrm{mex}$ とは $S$ 内に現れない最小の非負整数として定義され、 Grundy 数などと関係が深い値である.
実装は例えば値 $[0, n+1)$ の範囲をセグ木を用いて管理し、セグ木の各ノードで以下を管理する(今考えるノードに対応する値の範囲を $[l, r)$ とする).
$mid = (l + r) / 2$ としたとき $(x, y)$ を "$y = \min_{i \in [l, mid)}$ ($a_0, a_1, \dots, a_{x-1}$ のうちその値が $i$ となる最右の添字)" のように定める.
値が $i$ となるようなものがない場合は最右の添字を -1 とする).
すると $(x, y)$ は単調増加列をなし, 現在のノードに $(x, y)$ の狭義単調増加列を前計算しておきそれを保持する.
各範囲クエリに対してセグ木上で左右のどちらの子に下りるべきか($\mathrm{mex}$ の値が $[l, mid)$ or $[mid, r)$ のどちらの範囲に含まれるか) は前計算しておいた狭義単調増加列上で 2 分探索をすることで求めることができる.
よって全体として $\O(\log^2 n)$ の計算量でクエリに答えることができる.
以下の実装ではさらにフラクショナルカスケーディングを用いることで $\O(\log n)$ の計算量でクエリに答えるようにしている.
永続セグメント木を用いても同様の実装が可能.
時間計算量: 構築 $\O (n \log n)$, 各クエリ $\O (\log n)$
空間計算量: $\O (n \log n)$
コード
class RangeMexQuery {
private:
int n, m;
vector<array<int, 3> > ptr;
vector<int> arr, st;
int update(const int prv, const int id, const int val, const int l, const int r){
const int cur = (int)ptr.size();
ptr.push_back({0, 0, id});
if(r - l == 1) return cur;
const int mid = (l + r) / 2;
if(val < mid){
const int res = update(ptr[prv][0], id, val, l, mid);
ptr[cur][0] = res, ptr[cur][1] = ptr[prv][1];
}else{
const int res = update(ptr[prv][1], id, val, mid, r);
ptr[cur][0] = ptr[prv][0], ptr[cur][1] = res;
}
ptr[cur][2] = min(ptr[ptr[cur][0]][2], ptr[ptr[cur][1]][2]);
return cur;
}
void preprocessing(const vector<int>& vec){
arr[0] = 0;
for(int i = 0; i < n; ++i) arr[2 * i + 1] = vec[i], arr[2 * i + 2] = vec[i] + 1;
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
m = (int)arr.size(), st[0] = 0, ptr.push_back({0, 0, -1});
for(int i = 0; i < n; ++i){
const int val = (int)(lower_bound(arr.begin(), arr.end(), vec[i]) - arr.begin());
st[i + 1] = update(st[i], i, val, 0, m);
}
}
int query(const int cur, const int cri, const int l, const int r){
if(cur == 0 || r - l == 1) return arr[l];
const int mid = (l + r) / 2;
if(ptr[ptr[cur][0]][2] < cri) return query(ptr[cur][0], cri, l, mid);
else return query(ptr[cur][1], cri, mid, r);
}
public:
RangeMexQuery(const vector<int>& vec) : n((int)vec.size()), arr(2 * n + 1), st(n + 1){
preprocessing(vec);
}
int query(const int l, const int r){
return query(st[r], l, 0, m);
}
};
verify 用の問題
verify していません(verify 問題を知らない)