Range Mexクエリの効率的なアルゴリズムを教えてください

Question

私はこの問題について質問があります。

質問

• あなたはシーケンスa[0], a 1],..., a[N-1]を与え、そして範囲(l[i], r[i]) (0 <= i <= Q - 1)で設定されています。
• についてはmex(a[l[i]], a[l[i] + 1],..., a[r[i] - 1])と計算してください。

関数mexは最小除外値です。
Wikipedia Page of mex function

N <= 100000, Q <= 100000, and a[i] <= 100000とすることができます。
O(N * (r[i] - l[i]) log(r[i] - l[i]))アルゴリズムは明らかですが、効率的ではありません。

私の現在のアプローチ

#include <bits/stdc++.h> 
using namespace std; 
int N, Q, a[100009], l, r; 
int main() { 
    cin >> N >> Q; 
    for(int i = 0; i < N; i++) cin >> a[i]; 
    for(int i = 0; i < Q; i++) { 
     cin >> l >> r; 
     set<int> s; 
     for(int j = l; j < r; j++) s.insert(a[i]); 
     int ret = 0; 
     while(s.count(ret)) ret++; 
     cout << ret << endl; 
    } 
    return 0; 
} 

どのように解決する方法を教えてください。

EDIT：O（N^2）が遅い。より速いアルゴリズムを教えてください。

Answer 1

ここO((Q + N) log N)溶液は次のとおり

1. （セグメントツリーがそれぞれ最小値を格納すべきであるのは、左から右に、アレイ内のすべての位置を反復処理し、セグメントツリーの各値の最後のオカレンスを格納しようがノード）。

2. i番目の数字を追加した後、右の枠がiに等しいすべてのクエリに回答できます。

3. 答えは、last[x] < lのような最小値xです。ルートから始まるセグメントツリーを下に移動することによって見つけることができます（左の子の最小値がlより小さい場合はそこに行きます。そうでない場合、右の子に行きます）。

これだけです。ここで

は、いくつかの擬似コードです：

tree = new SegmentTree() // A minimum segment tree with -1 in each position 
for i = 0 .. n - 1 
    tree.put(a[i], i) 
    for all queries with r = i 
     ans for this query = tree.findFirstSmaller(l) 

見つける小さな関数はこのように書きます：

int findFirstSmaller(node, value) 
    if node.isLeaf() 
     return node.position() 
    if node.leftChild.minimum < value 
     return findFirstSmaller(node.leftChild, value) 
    return findFirstSmaller(node.rightChild) 

このソリューションでは、コードにかなり簡単です（あなたが必要とするすべてのポイントの更新とfindFisrtSmaller機能です

Answer 2

はここ

for (int i = 0; i < N; ++i) { 
    // 1. Add a[i] to all internal data structures 
    // 2. Calculate answers for all queries q such that r[q] == i 
} 

のようなものを私たちは、このループのO(N)反復を持っており、私たちはデータ構造の両方の更新をしたい、のは、左から右への方法で、私たちのクエリと私たちの両方の要素を処理しようとo(N)時間に現在処理されている部分の接尾辞を問い合せます。

は位置iから始まるサフィックスがそうでなければ数jと0が含まれている場合のは1を持つ配列contains[i][j]を使用してみましょう。また、それぞれcontains[i]の接頭辞の合計を計算したと考えてください。この場合、バイナリ検索を使用してO(log N)時間内の各特定のサフィックスクエリに答えることができます：対応するcontains[l[i]]配列の最初のゼロを見つける必要があります。これは部分和がインデックス+1でなくインデックス+1残念なことに、そのような配列はO(N^2)のスペースを必要とし、更新ごとにO(N^2)時間が必要です。

したがって、最適化する必要があります。 2次元のrange treeを "sum query"と "assignment"の範囲演算で構築しましょう。このようなツリーでは、任意の下位矩形の合計を照会し、O(log^2 N)時間内のすべての下位矩形のすべての要素に同じ値を割り当てることができます。O(log^2 N)時間で更新を実行し、O(log^3 N)時間でクエリを実行できます。 O(Nlog^2 N + Qlog^3 N)。空間複雑度O((N + Q)log^2 N)（およびアレイの初期化のための同じ時間）は、遅延初期化を使用して達成されます。

UP： "sum"を含む範囲ツリーでのクエリの動作を修正しましょう。（この答えは長すぎることはありませまで）1次元の木のために、このようなものです：

class Tree 
{ 
    int l, r;   // begin and end of the interval represented by this vertex 
    int sum;   // already calculated sum 
    int overriden;  // value of override or special constant 
    Tree *left, *right; // pointers to children 
} 
// returns sum of the part of this subtree that lies between from and to 
int Tree::get(int from, int to) 
{ 
    if (from > r || to < l) // no intersection 
    { 
     return 0; 
    } 
    if (l <= from && to <= r) // whole subtree lies within the interval 
    { 
     return sum; 
    } 
    if (overriden != NO_OVERRIDE) // should push override to children 
    { 
     left->overriden = right->overriden = overriden; 
     left->sum = right->sum = (r - l)/2 * overriden; 
     overriden = NO_OVERRIDE; 
    } 
    return left->get(from, to) + right->get(from, to); // split to 2 queries 
} 

私たちの特定のケースでは、ツリーのすべてのクエリは、プレフィックス合計クエリであることを考えると、fromは、常に0に等しく、だから、子どもへの呼び出しの1つは、些細な答え（0または既に計算されたsum）を返す。したがって、バイナリ検索アルゴリズムで2次元ツリーへのクエリO(log N)を実行する代わりに、このgetクエリと非常によく似た検索のためのアドホック手順を実装することができます。最初に左の子（既に計算されているのでO(1)が必要です）の値を取得してから、探しているノードが左にあるかどうかを確認する必要があります（この合計は左のサブツリーの葉の数よりも少ない）この情報に基づいて左または右に移動します。このアプローチでは、クエリがO(log^2 N)時間に最適化されます（今は1つのツリー操作なので）。O((N + Q)log^2 N))の時間と空間の複雑さをもたらします。

このソリューションは、QとNの両方で十分に高速であるとは確信していませんが、最大で10^5ですが、さらに最適化されている可能性があります。