Overview

After computing the final output \(F(s)\) for each input value \(s\), the problem asks us to answer, for each query \([A_j, B_j]\), the number of distinct values contained in the array \(F[A_j], F[A_j+1], \ldots, F[B_j]\).

Analysis

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

In the initial state, the signal value for input \(s\) is simply \(s\) itself, so:

\[ F(s) = s \]

At each step \((L_i, R_i, X_i)\), if the current signal value is between \(L_i\) and \(R_i\) (inclusive), it is replaced with \(X_i\).

In other words, if we maintain the current value \(F(s)\) for all \(s = 1, 2, \ldots, K\), and at each step update:

\[ F(s) = X_i \]

whenever

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

then we can obtain the final array \(F\).

At first glance, \(O(NK)\) seems large, but thanks to the constraint:

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

this part runs well within the time limit.

---

What we ultimately need is, for each query \([A, B]\), the number of distinct values in:

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

If we count this for each query using a set or similar structure, it takes in the worst case:

\[ O(QK) \]

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

Therefore, we handle this as a classic “number of distinct values in a range of a static array” problem.

Algorithm

1. Compute the final output array \(F\)

Prepare an array \(F\), initially set as:

\[ F[s] = s \]

Then, for each step \((L_i, R_i, X_i)\), iterate over all \(s\) and update:

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

This gives us the final output \(F(s)\) for all input values \(s\).

---

2. Count distinct values in a range using a Fenwick Tree

The problem now takes the following form:

Given an array \(F[1], F[2], \ldots, F[K]\),
for each query \([A, B]\), find the number of distinct values in the subarray \(F[A], \ldots, F[B]\).

We process this offline.

We process queries in increasing order of right endpoint \(B\).

We advance position pos from \(1\) to \(K\) sequentially.

At each point, the Fenwick Tree maintains the following information:

• For each value, place a \(1\) only at its last occurrence seen so far
• Set previous occurrences of the same value to \(0\)

For example, suppose the array is:

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

When we have processed up to pos = 5:

• The last occurrence of value \(1\) is at position \(4\)
• The last occurrence of value \(2\) is at position \(3\)
• The last occurrence of value \(3\) is at position \(5\)

So in the Fenwick Tree, positions \(3, 4, 5\) have a \(1\).

Now suppose a query \([A, B]\) has its right endpoint \(B\) equal to the current pos.

The number of distinct values in the range \([A, B]\) equals the sum in the Fenwick Tree over:

\[ [A, B] \]

This works because if a value appears in the range \([A, B]\), then its last occurrence must be at some position between \(A\) and \(B\) inclusive.

Conversely, if the last occurrence of a value is within \([A, B]\), then that value appears in the range.

---

The concrete procedure is as follows:

1. Group queries by their right endpoint \(B\)
2. Iterate pos from \(1\) to \(K\)
3. For the value v = F[pos]:
   • If v has appeared before, remove the \(1\) at its previous position
   • Add a \(1\) at the current position pos
   • Update last[v] = pos
4. For each query \([A, pos]\) with right endpoint equal to pos, compute the range sum in the Fenwick Tree

The range sum:

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

directly gives the answer.

Complexity

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

Since \(N \times K \leq 10^7\), directly simulating to obtain the final output array \(F\) is fast enough.

Implementation Notes

• The condition check at each step is applied to the current signal value \(F[s]\), not the original input value \(s\).

• Grouping queries by their right endpoint \(B\) allows us to answer them while scanning from left to right.

• In the Fenwick Tree, even if the same value appears at multiple positions, we place a \(1\) only at its last occurrence.

• Since all values are between \(1\) and \(K\) inclusive, a last array of size \(K+1\) is sufficient.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.