区間の種類数

クエリを右端 $r$ の小さい順に処理します。列を左から 1 つずつ見ていき、各値について、それまでで最後に出てきた位置にだけ $1$ を置いた列を BIT(Fenwick Tree)で持ちます。 $a_{r-1}$ まで見たとき、 $a_l, \ldots, a_{r-1}$ に含まれる値の種類数は、位置 $l$ 以上に置かれた $1$ の個数です。値 $x$ が区間に含まれることと、 $a_0, \ldots, a_{r-1}$ で $x$ が最後に出てきた位置が $l$ 以上であることは同じだからです。クエリを先にすべて読んでおく必要があります(オフライン)。

クエリを先読みできない(オンライン)ときは 永続セグ木 を使うと、1 クエリ $O(\log N)$ で答えられます。 $a_i$ を 1 つ見るごとに上の列を新しい版として残しておけば、区間 $[l, r)$ の答えは $a_{r-1}$ まで見た版の $[l, r)$ の和です(下の 2 つ目の例)。または、 $a_i$ と同じ値が $i$ より前に最後に出てきた位置を $p_i$(なければ $-1$)とすると、種類数は $l \le i < r$ かつ $p_i < l$ となる $i$ の個数なので、版 $i$ に $p_0, \ldots, p_{i-1}$ の値ごとの個数を持たせて(RangeKth と同じ形)、版 $r$ と版 $l$ の差から求めることもできます。

Mo’s algorithm のページの例と同じ問題で、そちらでも(オフラインで)求められますが、こちらの方が速いです。

例:

a = [1, 2, 1, 3, 2, 2]
print(range_count_distinct(a, [(0, 6), (1, 3), (2, 2), (3, 6), (5, 6)]))  # [3, 2, 0, 2, 1]

例(永続セグ木 の PersistentSegTree を使って、オンラインで答える):

seg = PersistentSegTree([0] * len(a), lambda x, y: x + y, 0)
ver = [0]  # ver[r] = a[r - 1] まで見た版
last = {}
for i, x in enumerate(a):
    v = ver[-1]
    if x in last:
        v = seg.set(v, last[x], 0)  # 前に出てきた位置の 1 を消す
    last[x] = i
    ver.append(seg.set(v, i, 1))
print(seg.prod(ver[6], 0, 6), seg.prod(ver[3], 1, 3))  # 3 2

コード

def range_count_distinct(a, queries):
    # queries = [(l, r), ...](半開区間 [l, r)、0 <= l <= r <= len(a))
    # a[l:r] に含まれる値の種類数を、クエリの順に並べたリストで返す(オフライン)
    n = len(a)
    q = len(queries)
    # 右端が r のクエリを head[r] から nxt でたどれるようにまとめる
    head = [-1] * (n + 1)
    nxt = [-1] * q
    for k in range(q):
        r = queries[k][1]
        nxt[k] = head[r]
        head[r] = k
    # 各値の、今までで最後に出てきた位置にだけ 1 を置いた列の BIT(位置は 1-indexed)
    bit = [0] * (n + 1)
    last = {}
    kinds = 0  # 今までに出てきた値の種類数
    res = [0] * q  # r = 0 のクエリの答えは 0 のまま
    for r in range(1, n + 1):
        x = a[r - 1]
        j = last.get(x, 0)
        if j:
            # 前に出てきた位置の 1 を消す
            while j <= n:
                bit[j] -= 1
                j += j & -j
        else:
            kinds += 1
        last[x] = r
        j = r
        while j <= n:
            bit[j] += 1
            j += j & -j
        # a[l:r] の種類数 = BIT の位置 l + 1 から r にある 1 の個数 = kinds - (位置 1 から l の和)
        k = head[r]
        while k != -1:
            j = queries[k][0]
            s = kinds
            while j:
                s -= bit[j]
                j -= j & -j
            res[k] = s
            k = nxt[k]
    return res