Mo's algorithm

クエリを左端のブロック（幅 $B = N / \sqrt{Q}$）ごとに分け、ブロックの中では右端の順に並べてから、今の区間の端を 1 つずつ動かして答えていきます。ブロックごとに右端の向きを交互に変えて、移動を減らしています。クエリを先にすべて読んでおく必要があります（オフライン）。

• mo(N, queries, add, remove, get): 長さ $N$ の列に対する区間クエリ queries = [(l, r), ...]（半開区間 $[l, r)$）の答えを、クエリの順に並べたリストで返す
• add(i), remove(i): 位置 $i$ を今の区間に加える関数・今の区間から除く関数
• get(k): 今の区間が $k$ 番目のクエリの区間になったときに呼ばれ、その答えを返す関数
• add_left, remove_left: 左端で出し入れするときの処理が右端と違うとき（区間の転倒数など）だけ渡す。省略すると add, remove を使う
• 計算量: add と remove を合わせて $O(N \sqrt{Q})$ 回、get を $Q$ 回呼ぶ

add と remove はとても多く呼ばれるので、中身はなるべく軽くします。

例（区間に含まれる値の種類数）:

cnt = [0] * (max(a) + 1)
kinds = 0


def add(i):
    global kinds
    cnt[a[i]] += 1
    if cnt[a[i]] == 1:
        kinds += 1


def remove(i):
    global kinds
    cnt[a[i]] -= 1
    if cnt[a[i]] == 0:
        kinds -= 1


ans = mo(n, queries, add, remove, lambda k: kinds)

コード

def mo(n, queries, add, remove, get, add_left=None, remove_left=None):
    # queries = [(l, r), ...]（半開区間 [l, r)、0 <= l <= r <= n）
    # add(i), remove(i): 位置 i を今の区間に加える・今の区間から除く
    # get(k): 今の区間を k 番目のクエリの区間としたときの答え
    # 左端での出し入れを右端と分けたいときは add_left, remove_left も渡す
    if add_left is None:
        add_left = add
    if remove_left is None:
        remove_left = remove
    q = len(queries)
    b = max(1, int(n / max(1, q) ** 0.5))
    key = []
    for l, r in queries:
        k = l // b
        key.append(k * (n + 1) + (r if k % 2 == 0 else n - r))
    res = [None] * q
    l = r = 0
    for k in sorted(range(q), key=key.__getitem__):
        ql, qr = queries[k]
        while l > ql:
            l -= 1
            add_left(l)
        while r < qr:
            add(r)
            r += 1
        while l < ql:
            remove_left(l)
            l += 1
        while r > qr:
            r -= 1
            remove(r)
        res[k] = get(k)
    return res