この問題の制約下で、ありえる入力信号値 \(s=1,2,\ldots,K\) すべてについて \(F(s)\) を求める \(O(NK)\) 時間の計算が十分高速に行えます。

よって、この問題は次のような問題に帰着されます。

長さ \(K\) の列 \((F _ 1,F _ 2,\ldots,F _ K)\) が与えられている。 次の形式の質問が \(Q\) 個与えられるので、すべてに答えよ。

• 整数 \(A,B\ (1\le A\le B\le K)\) に対して、連続する部分列 \((F _ A,F _ {A+1},\ldots,F _ B)\) に含まれる値の種類数を求めよ。

これは、\(B\) の昇順にクエリを並べ替え、平面走査を行いながら次のような列を管理することで解くことができます。

• 現在見ている右端 \(r\) に対して、\(c _ i\coloneqq r\lt i\) もしくは \(F _ i\) と等しい値が \(F _ {i+1},\ldots,F _ r\) に含まれるとき \(0\)、そうでないとき \(1\) となるような長さ \(K\) の列 \((c _ 1,c _ 2,\ldots,c _ N)\)

具体的には、区間 \([l,r]\) の種類数は \(c _ l+c _ {l+1}+\cdots+c _ r\) として求められ、\(r\) を \(1\) 増やすときには新しい \(r\) について \(c _ r\) を \(1\) にし、\(F _ p=F _ r\) を満たす \(r\) 未満の最大の \(p\) について \(c _ p\) を \(0\) にすればよいです。

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

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

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

    // ありえるすべての s について F(s) を求める
    vector<int> signal(K + 1);
    for (int i = 0; i <= K; ++i) {
        signal[i] = i;
    }
    for (int i = 0; i < N; ++i) {
        int L, R, X;
        cin >> L >> R >> X;
        for (int& s : signal) {
            if (L <= s && s <= R) { // 入力の信号値が内側なら
                s = X; // X に変換する
            }
        }
    }

    // クエリを先読み
    vector<tuple<int, int, int>> query(Q);
    for (int _i = 0; auto& [i, A, B] : query) {
        cin >> A >> B;
        i = _i++;
    }
    // B の昇順に並べ替える
    ranges::sort(query, {}, [](auto& q) { return get<2>(q); });

    // 平面走査
    vector previous(K + 1, -1); // previous[i] := 最後に i が出現したところ（まだ出現していなければ -1）
    atcoder::fenwick_tree<int> distinct(K + 1); // distinct[i] := i が最後の F[i] の出現なら 1 、そうでなければ 0
    vector<int> ans(Q);
    for (int i = 0, j = 0; i <= K; ++i) {
        // 値を更新し、
        distinct.add(i, 1);
        if (previous[signal[i]] != -1) {
            distinct.add(previous[signal[i]], -1);
        }
        previous[signal[i]] = i;

        // クエリに答える
        while (j < Q && get<2>(query[j]) == i) {
            auto [index, a, b] = query[j];
            ans[index] = distinct.sum(a, b + 1);
            ++j;
        }
    }
    for (int a : ans) {
        cout << a << endl;
    }
    return 0;
}

from atcoder.fenwicktree import FenwickTree


N, K, Q = map(int, input().split())

# ありえるすべての s について F(s) を求める
signal = [i for i in range(K + 1)]
for i in range(N):
    L, R, X = map(int, input().split())
    signal = [X if L <= s <= R else s for s in signal]

# クエリを先読み
query = []
for i in range(Q):
    A, B = map(int, input().split())
    query.append((i, A, B))
# B の昇順に並べ替える
query.sort(key=lambda x: x[2])

# 平面走査
previous = [-1 for i in range(K + 1)] # previous[i] := 最後に i が出現したところ（まだ出現していなければ -1）
distinct = FenwickTree(K + 1) # distinct[i] := i が最後の F[i] の出現なら 1 、そうでなければ 0
ans = [0 for i in range(Q)]

j = 0
for i in range(K + 1):
    # 値を更新して
    distinct.add(i, 1)
    if previous[signal[i]] != -1:
        distinct.add(previous[signal[i]], -1)
    previous[signal[i]] = i

    # クエリに答える
    while j < Q and query[j][2] == i:
        ans[query[j][0]] = distinct.sum(query[j][1], query[j][2] + 1)
        j += 1

print(*ans)