概要

\(N\) ステップの信号変換器に対して、各入力 \(s\) の出力 \(F(s)\) を求めた上で、クエリごとに区間 \([A_j, B_j]\) 内の \(F(s)\) の値の種類数（区間内の異なる値の個数）を効率的に数える問題です。

考察

ステップ1：\(F(s)\) の計算

まず、すべての入力値 \(s\) (\(1 \leq s \leq K\)) について出力 \(F(s)\) を求める必要があります。各 \(s\) について \(N\) ステップを素直にシミュレーションすれば、\(O(NK)\) で計算できます。制約に \(N \times K \leq 10^7\) とあるため、これは十分高速です。

例えば \(K=5\), \(N=2\) で、ステップが \((2, 4, 3)\) と \((3, 5, 1)\) のとき：

\(s\)	ステップ1後	ステップ2後 = \(F(s)\)
1	1	1
2	3	1
3	3	1
4	3	1
5	5	1

ステップ2：区間内の異なる値の個数

\(F(s)\) が求まったら、問題は「配列 \(F[1], F[2], \ldots, F[K]\) の区間 \([A_j, B_j]\) に含まれる異なる値の個数を求める」という有名問題に帰着されます。

素朴なアプローチ：各クエリごとに区間内をスキャンして集合に入れる → \(O(QK)\) で TLE の恐れ。

効率的なアプローチ：オフラインクエリ + BIT（Binary Indexed Tree） を使います。

アルゴリズム

「区間内の異なる値の個数」を求める定番テクニックを使います。

1. クエリを右端 \(B_j\) の昇順にソートする。
2. 配列 \(F\) を左から右へ走査（\(s = 1, 2, \ldots, K\)）する。
3. \(F[s] = v\) を見たとき：
   • もし値 \(v\) が以前に位置 \(\text{last}[v]\) で出現していたなら、BIT 上の位置 \(\text{last}[v]\) から \(-1\) する（古い出現を消す）。
   • BIT 上の位置 \(s\) に \(+1\) する（最新の出現を記録する）。
   • \(\text{last}[v] = s\) に更新する。
4. 走査位置 \(s\) がクエリの右端 \(B_j\) に達したら、BIT で区間 \([A_j, B_j]\) の合計を求める。

なぜこれで正しいか：

各値 \(v\) について、区間内での最も右の出現位置だけが BIT 上で \(+1\) されています。クエリ \([A_j, B_j]\) を処理する時点で、\(s \leq B_j\) の範囲の走査が完了しています。値 \(v\) が区間 \([A_j, B_j]\) に少なくとも1回出現するなら、その最右出現位置は \([A_j, B_j]\) 内にあるため、BIT の区間和で正しくカウントされます。

計算量

• 時間計算量: \(O(NK + K \log K + Q \log K)\)
  • \(F(s)\) の計算に \(O(NK)\)
  • 走査と BIT 操作に \(O(K \log K)\)
  • クエリ応答に \(O(Q \log K)\)
  • 制約 \(NK \leq 10^7\) より全体として十分高速
• 空間計算量: \(O(N + K + Q)\)

実装のポイント

• BIT（Fenwick Tree）の使い方：点更新（\(+1\) / \(-1\)）と区間和クエリを \(O(\log K)\) で処理できるデータ構造です。区間 \([l, r]\) の和は query(r) - query(l-1) で求められます。

• オフライン処理：クエリを右端でソートし、走査と同時に処理することで、各値の「最新の出現位置」のみを管理すればよくなります。

• last 配列：各値 \(v\) (\(1 \leq v \leq K\)) について、最後に \(F[s] = v\) となった位置 \(s\) を記録します。初期値は \(0\)（未出現）です。

  ソースコード

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

struct BIT {
    vector<int> tree;
    int n;
    BIT(int n) : n(n), tree(n+1, 0) {}
    void update(int i, int val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }
    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
    int query(int l, int r) {
        return query(r) - query(l-1);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    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];
    }
    
    // Compute F[s] for all s from 1 to K
    vector<int> F(K+1);
    for (int s = 1; s <= K; s++) {
        int v = s;
        for (int i = 0; i < N; i++) {
            if (L[i] <= v && v <= R[i]) {
                v = X[i];
            }
        }
        F[s] = v;
    }
    
    // Read queries
    vector<int> A(Q), B(Q), ans(Q);
    vector<pair<int,int>> queries(Q);
    for (int j = 0; j < Q; j++) {
        cin >> A[j] >> B[j];
        queries[j] = {B[j], j};
    }
    
    // Sort queries by right endpoint
    sort(queries.begin(), queries.end());
    
    // Process using BIT (offline, sweep right endpoint)
    BIT bit(K);
    vector<int> last(K+1, 0);
    int qi = 0;
    for (int s = 1; s <= K; s++) {
        int v = F[s];
        if (last[v] > 0) {
            bit.update(last[v], -1);
        }
        bit.update(s, 1);
        last[v] = s;
        
        while (qi < Q && queries[qi].first == s) {
            int j = queries[qi].second;
            ans[j] = bit.query(A[j], B[j]);
            qi++;
        }
    }
    
    for (int j = 0; j < Q; j++) {
        cout << ans[j] << '\n';
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。