Overview

First, we compute the final output \(F(s)\) for each input value \(s=1,2,\ldots,K\).
Then, we process the problem as finding the number of distinct values within the interval \([A_j,B_j]\) in the array \(F(1),F(2),\ldots,F(K)\).

Analysis

First, let’s consider the final output \(F(s)\) for each input value \(s\).

Since signal values range from \(1\) to \(K\), we can maintain the current value for all input values in an array.

For example,

arr[s] = the current value that input value s has become

Initially, nothing has been transformed, so

arr[s] = s

For each step \((L_i,R_i,X_i)\), we check all \(s=1,2,\ldots,K\):

• If \(L_i \leq arr[s] \leq R_i\), then \(arr[s]=X_i\)
• Otherwise, leave it unchanged

After all steps, arr[s] = F(s).

This might seem expensive, but since the constraint guarantees \(N \times K \leq 10^7\), this brute-force approach runs within the time limit.

---

Next, for each query, we need to find how many distinct values exist among

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

If we count using a set for each query, the worst case is

\(O(QK)\)

which is too slow since \(Q,K \leq 2 \times 10^5\).

Therefore, we use a classic technique for efficiently finding the “number of distinct values in a subarray.”

The key idea is as follows:

We scan the array from left to right, maintaining only the “last occurrence position” for each value.

For example, when the current position is \(i\), let last[v] be the last occurrence position of value \(v\).

Whether value \(v\) exists in the interval \([l,i]\) can be determined by:

last[v] >= l

In other words, for each value that has appeared so far, if its last occurrence position is at least \(l\), then it is contained in the interval \([l,i]\).

We manage this using a Fenwick Tree (BIT).

In the BIT, we

place a 1 only at the last occurrence position of each value

Then, when we have processed up to position \(i\):

• Let distinct be the number of distinct values that have appeared from position \(1\) to \(i\)
• Let BIT.sum(l-1) be the number of values whose last occurrence position is at most \(l-1\)

The number of distinct values in the interval \([l,i]\) is

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

This works because, among all values that have appeared so far, only those whose last occurrence position is at least \(l\) appear in the interval \([l,i]\).

Algorithm

1. Compute all \(F(s)\)

Prepare an array arr.

Initialize with:

arr[s] = s

For each transformation step \((L,R,X)\), check all \(s=1,2,\ldots,K\):

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

After all steps:

arr[s] = F(s)

---

2. Group queries by right endpoint \(B\)

Query \([A,B]\) is answered when we reach position \(B\) while scanning the array from left to right.

Therefore, we store queries in advance as:

queries[B].append((A, query_index))

---

3. Use BIT to find the number of distinct values in an interval

We process positions \(i=1,2,\ldots,K\) from left to right.

Let the current value be:

v = arr[i]

Case: value \(v\) has appeared before

Let the previous last occurrence position be prev = last[v].

Since we want “only a 1 at the last occurrence position” in the BIT, we remove the 1 at the old position prev:

BIT.add(prev, -1)

Then, place a 1 at the current position \(i\):

BIT.add(i, 1)

And update:

last[v] = i

Case: value \(v\) appears for the first time

A new value has appeared, so we increment distinct by 1:

distinct += 1

Then, place a 1 at the current position \(i\):

BIT.add(i, 1)

---

4. Answer queries with right endpoint \(i\)

The answer to query \([l,i]\) is:

distinct - BIT.sum(l - 1)

Here:

• distinct is the number of distinct values that have appeared from position \(1\) to \(i\)
• BIT.sum(l - 1) is the number of values whose last occurrence position is at most \(l-1\)

Therefore, by subtracting, we obtain “the number of values whose last occurrence position is at least \(l\)”, which is the number of distinct values appearing in the interval \([l,i]\).

Complexity

• Time complexity: \(O(NK + (K+Q)\log K)\)
• Space complexity: \(O(K+Q)\)

Since \(N \times K \leq 10^7\), computing all \(F(s)\) runs within the time limit.
Additionally, each query is processed in \(O(\log K)\) using the BIT.

Implementation Notes

• arr[s] represents the current signal value of input value \(s\).

• In the transformation process, the condition is checked against “the current signal value arr[s]”, not “the original input value \(s\)”.

• By grouping queries by their right endpoint \(B\), all queries can be processed in a single left-to-right scan.

• The BIT manages only the “latest occurrence position” of each value as a 1.

• When the same value appears again, remove the 1 at the old position before adding a 1 at the new position.

  Source Code

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()

---

This editorial was generated by gpt-5.5-high.