概要

各入力値 \(s\) に対する最終出力 \(F(s)\) を求めたあと、各質問 \([A_j, B_j]\) について配列 \(F[A_j], F[A_j+1], \ldots, F[B_j]\) に含まれる異なる値の個数を答える問題です。

考察

まず、入力値 \(s\) ごとに最終出力 \(F(s)\) を考えます。

初期状態では、入力値 \(s\) の信号値はそのまま \(s\) なので、

\[ F(s) = s \]

です。

各ステップ \((L_i, R_i, X_i)\) では、現在の信号値が \(L_i\) 以上 \(R_i\) 以下なら \(X_i\) に置き換えます。

つまり、すべての \(s = 1, 2, \ldots, K\) について現在の値 \(F(s)\) を持っておき、各ステップごとに

\[ L_i \leq F(s) \leq R_i \]

なら

\[ F(s) = X_i \]

と更新すれば、最終的な配列 \(F\) を求められます。

一見すると \(O(NK)\) は大きそうですが、制約に

\[ N \times K \leq 10^7 \]

があるため、この部分は十分間に合います。

---

最終的に必要なのは、各質問 \([A, B]\) に対して

\[ F(A), F(A+1), \ldots, F(B) \]

に含まれる異なる値の個数です。

これを各質問ごとに集合 set などで数えると、最悪で

\[ O(QK) \]

かかり、\(Q, K \leq 2 \times 10^5\) なので間に合いません。

そこで、これは典型的な「静的配列の区間内の異なる値の個数」を求める問題として処理します。

アルゴリズム

1. 最終出力配列 \(F\) を求める

配列 \(F\) を用意し、最初は

\[ F[s] = s \]

とします。

その後、各ステップ \((L_i, R_i, X_i)\) について、すべての \(s\) を見て、

if (L_i <= F[s] && F[s] <= R_i) {
    F[s] = X_i;
}

と更新します。

これで、すべての入力値 \(s\) に対する最終出力 \(F(s)\) が求まります。

---

2. 区間内の異なる値の個数を Fenwick Tree で求める

問題は次の形になります。

配列 \(F[1], F[2], \ldots, F[K]\) がある。
各質問 \([A, B]\) について、区間 \(F[A], \ldots, F[B]\) に含まれる異なる値の個数を求めよ。

これをオフラインで処理します。

右端 \(B\) が小さい順に見ていきます。

位置 pos を \(1\) から \(K\) まで順に進めます。

このとき、Fenwick Tree には次の情報を持たせます。

• 各値について、現在までに出現した「最後の位置」にだけ \(1\) を置く
• それ以前の同じ値の位置は \(0\) にする

例えば、配列が

\[ F = [2, 3, 2, 1, 3] \]

だったとします。

pos = 5 まで見たとき、

• 値 \(1\) の最後の出現位置は \(4\)
• 値 \(2\) の最後の出現位置は \(3\)
• 値 \(3\) の最後の出現位置は \(5\)

なので、Fenwick Tree 上では位置 \(3, 4, 5\) に \(1\) が立っています。

この状態で質問 \([A, B]\) の右端 \(B\) が現在の pos と等しいとします。

区間 \([A, B]\) に含まれる異なる値の個数は、Fenwick Tree 上の

\[ [A, B] \]

の和になります。

なぜなら、ある値が区間 \([A, B]\) に出現しているなら、その値の最後の出現位置は必ず \(A\) 以上 \(B\) 以下にあるからです。

逆に、その値の最後の出現位置が \([A, B]\) にあるなら、その値は区間内に出現しています。

---

具体的な処理は次の通りです。

1. 質問を右端 \(B\) ごとにまとめておく
2. pos = 1 から \(K\) まで順に見る
3. 値 v = F[pos] について、
   • 以前に v が出現していれば、その位置の \(1\) を削除する
   • 現在位置 pos に \(1\) を追加する
   • last[v] = pos と更新する
4. 右端が pos である質問 \([A, pos]\) に対し、Fenwick Tree の区間和を求める

区間和

\[ \text{sum}(A, pos) \]

がそのまま答えになります。

計算量

• 時間計算量: \(O(NK + (K + Q)\log K)\)
• 空間計算量: \(O(K + Q)\)

\(N \times K \leq 10^7\) なので、最終出力配列 \(F\) を直接シミュレーションしても間に合います。

実装のポイント

• ステップの条件判定は、元の入力値 \(s\) ではなく、現在の信号値 \(F[s]\) に対して行います。

• 質問は右端 \(B\) ごとにまとめておくと、左から走査しながら答えられます。

• Fenwick Tree では、同じ値の出現位置が複数あっても「最後の出現位置」にだけ \(1\) を置きます。

• 値はすべて \(1\) 以上 \(K\) 以下なので、last 配列のサイズは \(K+1\) で十分です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int sum(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    int range_sum(int l, int r) const {
        return sum(r) - sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    cin >> N >> K >> Q;

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

    vector<int> F(K + 1);
    for (int s = 1; s <= K; s++) F[s] = s;

    for (int i = 0; i < N; i++) {
        for (int s = 1; s <= K; s++) {
            if (L[i] <= F[s] && F[s] <= R[i]) {
                F[s] = X[i];
            }
        }
    }

    vector<vector<pair<int, int>>> queries(K + 1);
    for (int i = 0; i < Q; i++) {
        int A, B;
        cin >> A >> B;
        queries[B].push_back({A, i});
    }

    Fenwick fw(K);
    vector<int> last(K + 1, 0);
    vector<int> ans(Q);

    for (int pos = 1; pos <= K; pos++) {
        int v = F[pos];
        if (last[v] != 0) fw.add(last[v], -1);
        fw.add(pos, 1);
        last[v] = pos;

        for (auto [A, id] : queries[pos]) {
            ans[id] = fw.range_sum(A, pos);
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。