公式

E - 花の種類を数えよう / Count the Types of Flowers 解説 by MMNMM

この問題は、

  • 静的な列：列の内容が更新されない

への

  • オフライン：すべてのクエリを先に読むことができる

での「区間内の値の種類数を求める」クエリを処理する問題です。

この問題は、次の \(2\) つの方針で解くことができます。

  • Mo’s algorithm: 静的な列へのオフライン区間クエリに対するかなり汎用的なアルゴリズムです。
  • BIT (Fenwick Tree) を用いたアルゴリズム：区間種類数クエリの性質を利用したより計算量のよいアルゴリズムです。

この解説では、両方の方針について解説します。

1. Mo’s algorithm を用いた解法

Mo’s algorithm は、区間の端を \(1\) つ伸ばす・\(1\) つ縮める操作に対する結果を高速に処理できるときに、長さ \(N\) の静的な列に対する \(Q\) 個のオフライン区間クエリを \(O(N\sqrt Q)\) 回の伸ばす・縮める操作で処理するアルゴリズムです。

詳細に関しては Mo’s algorithm とその上位互換の話 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ や Mo’s algorithm - ei1333の日記 、Mo’s algorithm - アルゴリズムとデータ構造大全 などを参照してください。

Mo’s algorithm は、クエリを適切に並べ替えるパートと、並べ替えた順にクエリを伸ばす・縮める操作で処理するパートに分けることができます。 クエリを並べ替えるパートでは、ヒルベルト曲線を利用した順序など、いくつかの並べ替え方が提案されています。 クエリの良い並べ替え方を考えることは、マンハッタン距離上の巡回セールスマン問題（のちょっとした変種）に対してよい解を与えることだと考えることもできます。

実装例は以下のようになります。

実装例

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> P(N);
    for (auto&& p : P) {
        cin >> p;
        --p;
    }

    vector<pair<int, int>> queries(Q);
    for (auto&& [L, R] : queries) {
        cin >> L >> R;
        --L; // 0-indexed の半開区間にしておく
    }

    vector query_index(views::iota(0, N) | ranges::to<vector>()); // クエリ番号を並べ替える
    ranges::sort(query_index, {}, [&queries](const auto& i) {
        const auto& [L, R] = queries[i];
        return make_pair(L / 512, L & 512 ? R : ~R); // L を分割して、L での分割の偶奇に応じて R の昇順か降順かを決める
    });
    
    vector<int> ans(Q); // 答えを入れる配列

    vector<int> count(N); // count[i] := 区間内に i が何回出ているか
    int now_distinct_count = 0; // now_distinct_count := 区間内に何種類の値があるか
    int l = 0, r = 0; // 現在の区間 [l, r)
    for (const auto i : query_index) {
        const auto& [L, R] = queries[i]; // 並べ替えた順番にクエリを見る
        
        // 伸縮して区間を合わせる
        while (l < L)
            now_distinct_count -= !--count[P[l++]];
        while (l > L)
            now_distinct_count += !count[P[--l]]++;
        while (r < R)
            now_distinct_count += !count[P[r++]]++;
        while (r > R)
            now_distinct_count -= !--count[P[--r]];
        
        ans[i] = now_distinct_count;
    }

    // 答えを出力
    for (const auto a : ans)
        cout << a << endl;
    return 0;
}

N, Q = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P] # 0-indexed にしておく

queries = [tuple(map(int, input().split())) for _ in range(Q)]
queries = [(i, query[0] - 1, query[1]) for i, query in enumerate(queries)] #  0-indexed の半開区間にして、クエリ番号もつけておく

queries.sort(key = lambda x: (x[1] // 512, x[2] if x[1] & 512 else -x[2])) # L を分割して、L での分割の偶奇に応じて R の昇順か降順かを決める

ans = [0 for _ in range(Q)] # 答えを入れるリスト

count = [0 for _ in range(N)] # count[i] := 区間内に i が何回出ているか
now_distinct_count = 0; # now_distinct_count := 区間内に何種類の値があるか
l = 0
r = 0 # 現在の区間 [l, r)

for i, L, R in queries: # 並べ替えた順番にクエリを見る
    # 伸縮して区間を合わせる
    while l < L:
        count[P[l]] -= 1
        if count[P[l]] == 0:
            now_distinct_count -= 1
        l += 1
    while l > L:
        l -= 1
        if count[P[l]] == 0:
            now_distinct_count += 1
        count[P[l]] += 1
    while r < R:
        if count[P[r]] == 0:
            now_distinct_count += 1
        count[P[r]] += 1
        r += 1
    while r > R:
        r -= 1
        count[P[r]] -= 1
        if count[P[r]] == 0:
            now_distinct_count -= 1

    ans[i] = now_distinct_count

# 答えを出力
print(*ans)

2. BIT (Fenwick Tree) を用いた解法

クエリをすべて \(R _ i\) の昇順に並べ替えておきます。

\(r=1,2,\ldots,N\) の順に次のような処理を行うことを考えます。

  • \(i=1,2,\ldots,N\) に対して、\(1\le i\le r\) かつ、\(i\lt j\le r\) を満たすすべての整数 \(j\) について \(P _ i\ne P _ j\) のとき \(B _ i=1\) 、そうでないとき \(B _ i=0\) であるような列 \(B=(B _ 1,B _ 2,\ldots,B _ N)\) を用意する。
  • \(R _ i=r\) であるようなクエリに対して答えを求める。答えは \(\displaystyle\sum _ {k=L _ i} ^ {R _ i}B _ k\) である。

数列 \(B\) は「\(P _ 1,P _ 2,\ldots,P _ r\) まで順に見たとき、その値が最後に出てきたところなら \(1\) 、そうでなければ \(0\)」で定まる数列です。 このようにして得られる答えが正しいことを確かめます。

区間 \(\lbrack L _ i,R _ i\rbrack\) に含まれる整数 \(k\) に対する \(P _ k\) の集合は、\(B _ k=1\) であるような \(L _ i\le k\le R _ i\) に対する \(P _ k\) の集合と一致します。

証明

後者が前者に含まれることは明らかです。

前者に含まれ、後者に含まれない要素があると仮定して矛盾を示します。 そのような値に対応する \(P _ k\) のうち、\(k\) が最大のものを選びます。

\(P _ k\) が後者の集合に含まれないことから、\(B _ k=0\) です。 \(B _ k\) の定義から、\(k\lt j\le r\) を満たすある整数 \(j\) が存在して \(P _ k=P _ j\) を満たします。 \(k\) の最大性から \(B _ j=1\) ですが、後者の集合は \(P _ j\) を含むことになるので矛盾です。 よって、示されました。

\(B _ k\) の定義から、\(B _ {k _ 0}=1,B _ {k _ 1}=1\) であるような \(L _ i\le k _ 0\lt k _ 1\le R _ i\) について \(P _ {k _ 0}\ne P _ {k _ 1}\) が成り立ちます。 よって、求める集合のサイズは \(B _ k\) の総和と等しいことが示されました。

あとは、このような処理が高速に行えればよいです。

\(B\) を BIT (Fenwick Tree) で管理することを考えます。 \(\displaystyle\sum _ {k=L _ i} ^ {R _ i}B _ k\) は \(O(\log N)\) 時間で求めることができます。 \(r\) を増やしたときに \(B\) のうち変化する部分はたかだか \(2\) 箇所なので、BIT を使いまわしてたかだか \(2\) 箇所だけ更新することで十分高速に \(B\) を管理することができます。

時間計算量は \(O((N+Q)\log N)\) となります。

実装例は以下のようになります。

実装例

#include <iostream>
#include <vector>
#include <optional>
#include <ranges>
#include <utility>
#include <algorithm>
#include <atcoder/fenwicktree>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<int> P(N);
    for (auto&& p : P) {
        cin >> p;
        --p;
    }

    vector<pair<int, int>> queries(Q);
    for (auto&& [L, R] : queries) {
        cin >> L >> R;
        --L; // 0-indexed の半開区間にしておく
    }
    vector query_index(views::iota(0, Q) | ranges::to<vector>()); // クエリ番号を並べ替える
    ranges::sort(query_index, greater{}, [&queries](const auto i){return queries[i].second;}); // R で並べ替える

    vector<int> ans(Q); // 答えを入れる配列

    vector<optional<int>> previous_appear(N); // 直前に登場したのはどこか（登場していなければ std::nullopt）
    atcoder::fenwick_tree<int> bit(N); // 最後に登場したところに 1 が立っている BIT

    for (const auto& [r, p] : views::enumerate(P)) { // 順番に P を見ていく
        if (previous_appear[p]) // すでに P[r] が出てきていたら
            bit.add(*previous_appear[p], -1); // 前のところを 0 にする
        bit.add(r, 1); // 今のところを 1 にして、
        previous_appear[p] = r; // 直前の出現箇所を更新

        // 右端が r + 1 (r は 0-indexed なので) のクエリを全部処理する
        while (!empty(query_index) && queries[query_index.back()].second == r + 1) {
            const auto i = query_index.back();
            query_index.pop_back();
            const auto [L, R] = queries[i];
            ans[i] = bit.sum(L, R);
        }
    }

    // 答えを出力
    for (const auto a : ans)
        cout << a << endl;

    return 0;
}

from atcoder.fenwicktree import FenwickTree


N, Q = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P] # 0-indexed にしておく

queries = [tuple(map(int, input().split())) for _ in range(Q)]
queries = [(i, query[0] - 1, query[1]) for i, query in enumerate(queries)] #  0-indexed の半開区間にして、クエリ番号もつけておく

queries.sort(key = lambda x: x[2]) # R の昇順で並べ替える

ans = [0 for _ in range(Q)] # 答えを入れるリスト

previous_appear = [-1 for _ in range(N)] # 直前に登場したのはどこか（登場していなければ -1）
bit = FenwickTree(N) # 最後に登場したところに 1 が立っている BIT
now = 0 # クエリを先頭からいくつ処理したか

for r, p in enumerate(P): # 順番に P を見ていく
    if previous_appear[p] > -1: # すでに P[r] が出てきていたら
        bit.add(previous_appear[p], -1) # 前のところを 0 にする
    bit.add(r, 1) # 今のところを 1 にして、
    previous_appear[p] = r # 直前の出現箇所を更新

    # 右端が r + 1 （r は 0-indexed なので）のクエリを全部処理する
    while now < Q and queries[now][2] == r + 1:
        i, L, R = queries[now]
        ans[i] = bit.sum(L, R)
        now += 1

# 答えを出力
print(*ans)

投稿日時:
最終更新: