概要

\(N\) 回の変換ステップを経て、初期値 \(s \in [1, K]\) が最終的にどの値 \(F(s)\) に変換されるかを効率的に求め、その結果に対して「範囲 \([A_j, B_j]\) に含まれる \(F(s)\) の種類数」を答える問題です。

考察

1. 変換プロセスの効率化

素直に各ステップで全ての信号値を更新すると、最悪計算量が \(O(NK)\) となり、制約下（\(N, K \leq 2 \times 10^5\)）では間に合いません。 ここで、「同じ値を持っている信号たちは、その後の変換でも常に同じ挙動をする」という性質に注目します。

初期状態では \(1, 2, \dots, K\) はすべて異なる値ですが、あるステップで範囲 \([L_i, R_i]\) に含まれる値はすべて \(X_i\) に書き換えられ、一つのグループに統合されます。この「グループの統合」を管理するには DSU (Union-Find) が適しています。

2. 信号値の追跡

現在変換器内に存在する「異なる値」を std::set などのデータ構造で管理します。 各ステップ \((L_i, R_i, X_i)\) では以下の操作を行います。 1. set から \([L_i, R_i]\) の範囲にある値をすべて見つける。 2. それらの値を set から削除し、DSU で一つのグループに統合する。 3. 統合されたグループの代表値が指す現在の値を \(X_i\) とし、set に \(X_i\) を追加する。

この方法では、一度統合された値は二度と分かれないため、set への追加・削除回数の合計は \(O(N+K)\) 回に抑えられます。

3. 範囲内の種類数クエリ

すべてのステップが終了すると、各 \(s\) に対する最終的な出力 \(F(s)\) が確定します。次に、配列 \(F\) の特定区間 \([A_j, B_j]\) における種類数を求める必要があります。これは競技プログラミングにおける典型問題で、オフラインクエリと Fenwick Tree (BIT) を用いて解くことができます。

• クエリを右端 \(B_j\) の昇順にソートします。
• 配列を左から順に走査し、各値について「最後に現れた位置」を記録します。
• 新しい位置 \(i\) で値 \(v\) が現れたとき：
  • 以前に \(v\) が現れた位置があれば、BIT のその位置から \(1\) を引く。
  • 現在の位置 \(i\) に BIT で \(1\) を加える。
• この状態で BIT の区間 \([A_j, B_j]\) の和を求めれば、それが種類数となります。

アルゴリズム

1. DSU と Set によるシミュレーション

   • pos[v] : 値 \(v\) を持っている初期値のグループ（DSUの根）。
   • current_value[root] : DSUの根 root が現在持っている信号値。
   • S : 現在変換器内に存在する信号値の集合。
   • 各ステップで S.lower_bound(L_i) を使い、範囲内の値を一括して統合・更新する。

2. オフライン種類数カウント

   • 全ステップ終了後の \(F(s)\) を配列に格納。
   • クエリを \(B_j\) でソートし、BIT を用いて走査しながら種類数を計算する。

計算量

• 時間計算量: \(O((N + K + Q) \log K)\)
  • シミュレーション部分：各要素が set に追加・削除される回数は高々定数回のため \(O((N+K) \log K)\)。
  • 種類数クエリ部分：ソートと BIT 操作で \(O((K+Q) \log K)\)。
• 空間計算量: \(O(N + K + Q)\)
  • DSU、BIT、配列 \(F\)、クエリの保存に要するメモリ。

実装のポイント

• Set のイテレータ管理: set から範囲内の要素を削除する際、イテレータが無効化されないよう、一旦削除対象をリストアップしてから削除を行う必要があります。

• DSU の活用: 複数の初期値が同じ値に収束していく様子を unite 操作で表現します。

• 1-indexed と 0-indexed: BIT や入力値の範囲（\(1 \dots K\)）に合わせてインデックスの扱いに注意してください。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <set>
#include <algorithm>

using namespace std;

/**
 * Disjoint Set Union (DSU) to keep track of initial values that map to the same current value.
 */
struct DSU {
    vector<int> parent;
    vector<int> rnk;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        rnk.resize(n + 1, 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    int unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (rnk[root_i] < rnk[root_j]) {
                parent[root_i] = root_j;
                return root_j;
            } else {
                parent[root_j] = root_i;
                if (rnk[root_i] == rnk[root_j]) rnk[root_i]++;
                return root_i;
            }
        }
        return root_i;
    }
};

/**
 * Fenwick Tree (Binary Indexed Tree) for range distinct value queries.
 */
struct FenwickTree {
    int n;
    vector<int> tree;
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
    void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    if (!(cin >> N >> K >> Q)) return 0;

    vector<int> L(N), R(N), X(N);
    for (int i = 0; i < N; ++i) {
        cin >> L[i] >> R[i] >> X[i];
    }

    // Set of currently active values in the transformer
    set<int> S;
    // Mapping from a value to the root of its DSU component
    vector<int> pos(K + 1, -1);
    // Mapping from the root of a DSU component to its current value
    vector<int> current_value(K + 1);
    DSU dsu(K);

    // Initial state: each value s from 1 to K is its own component with value s
    for (int v = 1; v <= K; ++v) {
        S.insert(v);
        pos[v] = v;
        current_value[v] = v;
    }

    // Process each transformation step
    for (int i = 0; i < N; ++i) {
        auto it = S.lower_bound(L[i]);
        vector<int> to_merge;
        while (it != S.end() && *it <= R[i]) {
            to_merge.push_back(*it);
            it++;
        }
        if (to_merge.empty()) continue;

        int target_v = X[i];
        int root_of_target;

        if (S.count(target_v)) {
            root_of_target = dsu.find(pos[target_v]);
        } else {
            // target_v is not currently active, so move one component to target_v
            int v0 = to_merge.back();
            to_merge.pop_back();
            root_of_target = dsu.find(pos[v0]);
            S.erase(v0);
            pos[v0] = -1;
            S.insert(target_v);
            pos[target_v] = root_of_target;
            current_value[root_of_target] = target_v;
        }

        // Merge all other components in the range [L_i, R_i] into the target_v component
        for (int v : to_merge) {
            if (v == target_v) continue;
            int root_v = dsu.find(pos[v]);
            root_of_target = dsu.unite(root_v, root_of_target);
            S.erase(v);
            pos[v] = -1;
            pos[target_v] = root_of_target;
            current_value[root_of_target] = target_v;
        }
    }

    // Compute the final value F(s) for each initial signal s
    vector<int> F(K);
    for (int s = 1; s <= K; ++s) {
        F[s - 1] = current_value[dsu.find(s)];
    }

    // Answer range distinct queries offline using a Fenwick tree
    vector<vector<pair<int, int>>> queries_at(K + 1);
    for (int j = 0; j < Q; ++j) {
        int a, b;
        cin >> a >> b;
        queries_at[b].push_back({a, j});
    }

    vector<int> last_pos(K + 1, 0);
    FenwickTree ft(K);
    vector<int> results(Q);
    for (int i = 1; i <= K; ++i) {
        int val = F[i - 1];
        if (last_pos[val] != 0) {
            // Remove the contribution of the previous occurrence of this value
            ft.add(last_pos[val], -1);
        }
        // Add the contribution of the current occurrence
        ft.add(i, 1);
        last_pos[val] = i;

        // Process all queries ending at the current position i
        for (auto& q : queries_at[i]) {
            int left = q.first;
            int idx = q.second;
            // The number of distinct values in F[left-1...i-1] is the number of values
            // whose last occurrence in F[0...i-1] is at an index in [left-1, i-1].
            results[idx] = ft.query(i) - ft.query(left - 1);
        }
    }

    // Print the results for each query
    for (int j = 0; j < Q; ++j) {
        cout << results[j] << "\n";
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。