概要

各入力値 \(s=1,2,\ldots,K\) に対する最終出力 \(F(s)\) をまず全て求めます。
その後、配列 \(F(1),F(2),\ldots,F(K)\) に対して、区間 \([A_j,B_j]\) に含まれる値の種類数を答える問題として処理します。

考察

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

信号値の範囲は \(1\) 以上 \(K\) 以下なので、全ての入力値について現在の値を配列で持つことができます。

例えば、

arr[s] = 入力値 s が現在どの値になっているか

とします。

最初は何も変換されていないので、

arr[s] = s

です。

各ステップ \((L_i,R_i,X_i)\) について、全ての \(s=1,2,\ldots,K\) を見て、

• もし \(L_i \leq arr[s] \leq R_i\) なら \(arr[s]=X_i\)
• そうでなければそのまま

とすれば、最終的に arr[s] = F(s) になります。

一見重そうですが、制約に \(N \times K \leq 10^7\) があるため、この全探索は十分間に合います。

---

次に、各クエリでは

arr[A], arr[A+1], ..., arr[B]

の中に何種類の値があるかを求めればよいです。

これをクエリごとに集合 set で数えると、最悪で

\(O(QK)\)

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

そこで、配列の「区間内の異なる値の個数」を高速に求める典型手法を使います。

重要な考え方は次の通りです。

左から右へ配列を走査しながら、各値について「最後に出現した位置」だけを管理します。

例えば、現在位置が \(i\) のとき、値 \(v\) の最後の出現位置を last[v] とします。

区間 \([l,i]\) に値 \(v\) が存在するかどうかは、

last[v] >= l

で判定できます。

つまり、現在までに出現した各値について、その最後の出現位置が \(l\) 以上なら、区間 \([l,i]\) に含まれているということです。

これを Fenwick Tree、つまり BIT で管理します。

BIT には、

各値の最後の出現位置にだけ 1 を立てる

ようにします。

すると、現在位置 \(i\) まで見たとき、

• 現在までに出現した値の種類数を distinct
• 最後の出現位置が \(l-1\) 以下の値の個数を BIT.sum(l-1)

とすると、区間 \([l,i]\) に含まれる値の種類数は

\(distinct - BIT.sum(l-1)\)

になります。

なぜなら、現在までに出現した値のうち、最後の出現位置が \(l\) 以上のものだけが区間 \([l,i]\) に現れるからです。

アルゴリズム

1. 全ての \(F(s)\) を求める

配列 arr を用意します。

arr[s] = s

で初期化します。

各変換ステップ \((L,R,X)\) について、全ての \(s=1,2,\ldots,K\) を調べます。

if L <= arr[s] <= R:
    arr[s] = X

これにより、全ステップ後には

arr[s] = F(s)

になります。

---

2. クエリを右端 \(B\) ごとにまとめる

クエリ \([A,B]\) は、配列を左から走査していて位置 \(B\) に到達したときに答えます。

そのため、あらかじめ

queries[B].append((A, クエリ番号))

のように保存しておきます。

---

3. BIT で区間内の異なる値の個数を求める

左から順に \(i=1,2,\ldots,K\) を見ていきます。

現在の値を

v = arr[i]

とします。

値 \(v\) が以前に出現していた場合

以前の最後の出現位置を prev = last[v] とします。

BIT では「最後の出現位置にだけ 1」を置きたいので、古い位置 prev の 1 を消します。

BIT.add(prev, -1)

その後、現在位置 \(i\) に 1 を立てます。

BIT.add(i, 1)

そして、

last[v] = i

に更新します。

値 \(v\) が初めて出現した場合

新しい値が増えたので、種類数 distinct を 1 増やします。

distinct += 1

そして、現在位置 \(i\) に 1 を立てます。

BIT.add(i, 1)

---

4. 右端が \(i\) のクエリに答える

クエリ \([l,i]\) に対する答えは、

distinct - BIT.sum(l - 1)

です。

ここで、

• distinct は、位置 \(1\) から \(i\) までに出現した値の種類数
• BIT.sum(l - 1) は、最後の出現位置が \(l-1\) 以下の値の個数

です。

したがって、それらを引くことで「最後の出現位置が \(l\) 以上の値の個数」、つまり区間 \([l,i]\) に現れる値の種類数が求まります。

計算量

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

\(N \times K \leq 10^7\) なので、\(F(s)\) を全て求める部分は間に合います。
また、各クエリは BIT により \(O(\log K)\) で処理できます。

実装のポイント

• arr[s] は入力値 \(s\) の現在の信号値を表します。

• 変換処理では、条件判定に使うのは「元の入力値 \(s\)」ではなく「現在の信号値 arr[s]」です。

• クエリは右端 \(B\) ごとにまとめておくと、左から 1 回走査するだけで全て処理できます。

• BIT には「各値の最新出現位置」だけを 1 として管理します。

• 同じ値が再び出現したら、古い位置の 1 を削除してから新しい位置に 1 を追加します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K, Q = data[0], data[1], data[2]
    idx = 3

    arr = list(range(K + 1))
    positions = range(1, K + 1)

    for _ in range(N):
        L = data[idx]
        R = data[idx + 1]
        X = data[idx + 2]
        idx += 3

        a = arr
        for p in positions:
            v = a[p]
            if L <= v <= R:
                a[p] = X

    queries = [[] for _ in range(K + 1)]
    for qi in range(Q):
        A = data[idx]
        B = data[idx + 1]
        idx += 2
        queries[B].append((A, qi))

    bit = [0] * (K + 2)
    last = [0] * (K + 1)
    ans = [0] * Q
    distinct = 0

    for i in range(1, K + 1):
        v = arr[i]
        prev = last[v]

        if prev:
            x = prev
            while x <= K:
                bit[x] -= 1
                x += x & -x
        else:
            distinct += 1

        x = i
        while x <= K:
            bit[x] += 1
            x += x & -x

        last[v] = i

        for l, qi in queries[i]:
            s = 0
            x = l - 1
            while x > 0:
                s += bit[x]
                x -= x & -x
            ans[qi] = distinct - s

    print("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

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