Mo's algorithm
コードについての説明
Segment Tree ではうまく処理できない($2$ つの範囲の結果を結合することが難しい)ような範囲に関するクエリで, 更新がなくまた今の範囲を $1$ つ伸ばしたり, $1$ つ縮めたりという操作は簡単にできるという場合に用いることのできる手法.
配列の長さ $n$ を $\sqrt{n}$ 個のブロックに分け, すべてのクエリをその範囲の左端に注目して対応するブロックに振り分ける(各ブロック内では右端が昇順(偶数ブロック)または降順(奇数ブロック)になるようにクエリを並び替える).
そのようにクエリを並び替えてあとは順番にクエリを伸縮させながら処理していくと, 結局範囲の伸縮の回数が $\O ((n+q) \sqrt{n})$ 回で抑えられるという寸法.
こちら を参考に実装しました.
原理上このアルゴリズムは $n(\ge 3)$ 次元にも拡張でき, 特に更新がある場合の範囲クエリは $3$ 次元に Mo's algorithm を拡張することで処理が可能である.
更新および範囲クエリの数が $\Theta \left( n \right)$ であるときブロック幅を $n^{2 / 3}$ として $xy$ 平面を $n^{1/3} \times n^{1/3}$ のブロックに分割して $z$ 方向にたどることで全体で
$\O \left( n^{5/3} \ast K \right)$ 時間($K$ は範囲の伸縮一回にかかる計算量) ですべてのクエリを処理することが可能である(参考問題 および コード).
(関数)
$insert(l, r)$ : 範囲 $[l, r)$ に関するクエリを突っ込む
$solve()$ : すべてのクエリを insert したあとに計算する(ans にクエリの答えが格納される)
$add()$, $del()$ : 一回の範囲の縮小の際に行う計算(クエリの内容により変更する)
時間計算量: $\O ((n+q) \sqrt{n} \ast K)$ ($q$ はクエリの数, $K$ は範囲の伸縮一回にかかる計算量)
コード
// insert→solveでansに全クエリに対する結果が格納
// add,del を変更していろいろなクエリに対応する
// 以下は区間内の数の種類数についてのクエリが飛んでくる場合
//現在の状態および値
const int MAX_VAL = 30000;
int a[MAX_VAL]; //要素
int cnt[MAX_VAL]; //区間内のiの個数
int res; //区間内の種類の数
class Mo{
private:
vector<int> left, right;
const int width;
void add(const int id);
void del(const int id);
public:
vector<int> ans;
Mo(const int n) : width((int)sqrt(n)){}
//クエリ[l,r)
void insert(const int l, const int r){
left.push_back(l), right.push_back(r);
}
void solve(){
const int sz = (int)left.size();
int nl = 0, nr = 0;
vector<int> ord(sz);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](const int a, const int b){
const int c = left[a] / width, d = left[b] / width;
return (c == d) ? ((c & 1) ? (right[b] < right[a]) : (right[a] < right[b])) : (c < d);
});
ans.resize(sz);
for(const int id : ord){
while(nl > left[id]) add(--nl);
while(nr < right[id]) add(nr++);
while(nl < left[id]) del(nl++);
while(nr > right[id]) del(--nr);
ans[id] = res;
}
}
};
//idは元の配列のインデックス
void Mo::add(const int id)
{
++cnt[a[id]];
if(cnt[a[id]] == 1) ++res;
}
void Mo::del(const int id)
{
--cnt[a[id]];
if(cnt[a[id]] == 0) --res;
}
verify 用の問題
Atcoder : ニワンゴくんの約数
提出コード (愚直なので TL が厳しめ)
Atcoder : Range Set Query
提出コード