区間の種類数
クエリを右端 $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$ 以上であることは同じだからです。クエリを先にすべて読んでおく必要があります(オフライン)。
range_count_distinct(a, queries): 列 $a$ と区間のリストqueries = [(l, r), ...](半開区間 $[l, r)$、 $0 \le l \le r \le N$)について、a[l:r]に含まれる値の種類数をクエリの順に並べたリストで返す。値はハッシュできれば何でもよい。 $O((N + Q) \log N)$
クエリを先読みできない(オンライン)ときは 永続セグ木 を使うと、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