Summary

This problem asks us to find the total number of contiguous intervals \([l, r]\) that contain all \(7\) types of stamps from a sequence of length \(N\), where stamps are represented by integers from \(1\) to \(7\).

Analysis

Naive Approach and Its Limitations

One possible approach is to enumerate all pairs of intervals \((l, r)\) (\(1 \le l \le r \le N\)) and check whether each contains all numbers from \(1\) to \(7\). However, there are \(\frac{N(N+1)}{2}\) possible intervals (\(O(N^2)\) possibilities) just by choosing the endpoints. In this problem, \(N \le 10^6\), so the total number of intervals reaches approximately \(5 \times 10^{11}\), which will certainly exceed the time limit (TLE).

Fixing the Right Endpoint \(r\)

To count efficiently, let us consider fixing the right endpoint \(r\) of the interval and iterating \(r\) from \(1\) to \(N\).

When the right endpoint is fixed at \(r\), let us determine the condition for a valid left endpoint \(l\) (\(1 \le l \le r\)). For the interval \([l, r]\) to contain stamp type \(k\) (\(1 \le k \le 7\)), the most recent occurrence of type \(k\) at or before \(r\) must be greater than or equal to \(l\).

Therefore, letting \(P_k\) be the latest position where type \(k\) appears at or before \(r\), the condition that interval \([l, r]\) contains all types \(1 \le k \le 7\) is: $\(l \le P_1 \text{ and } l \le P_2 \text{ and } \dots \text{ and } l \le P_7\)$

If we define \(M = \min(P_1, P_2, \dots, P_7)\) as the minimum of the latest occurrence positions, this can be rewritten as: $\(1 \le l \le M\)$

In other words, for a fixed right endpoint \(r\), the number of valid left endpoints \(l\) is exactly \(M\). Note that if some stamp type has not appeared yet, we can set its latest position to \(0\). In this case, \(M = 0\), which naturally represents that there are \(0\) valid values for \(l\).

Algorithm

1. Prepare an array last_pos to store the most recent position of each stamp type \(1 \dots 7\), initialized to all \(0\)s.
2. Initialize a variable ans to \(0\) to store the cumulative answer.
3. For each \(r = 1, 2, \dots, N\) in order, perform the following:
   • Update the latest position of \(C_r\) to \(r\) (last_pos[C_r] = r).
   • Find the minimum of the latest positions across all types: \(M = \min_{1 \le i \le 7} \text{last\_pos}[i]\).
   • Add \(M\) to ans.
4. Output the final value of ans.

Complexity

• Time Complexity: \(O(NK)\) (where \(K\) is the number of stamp types; here, \(K = 7\))
  • As we iterate \(r\) from \(1\) to \(N\), finding the minimum of an array of size \(7\) takes \(O(K)\) time per step. The overall time complexity is \(O(7N)\), requiring approximately \(7 \times 10^6\) operations, which runs well within the time limit.
• Space Complexity: \(O(K)\)
  • It only requires maintaining an array last_pos of size \(8\) and a few variables, which is \(O(1)\) (or \(O(K)\)).

Implementation Details

• Beware of Integer Overflow: The total number of valid intervals can be up to approximately \(\frac{N(N+1)}{2} \approx 5 \times 10^{11}\). This exceeds the maximum value of standard 32-bit signed integer types (about \(2 \times 10^9\)) and causes an overflow; therefore, the variable ans used to accumulate the answer must be a 64-bit integer type (long long in C++).

• Handling Unseen Stamp Types: By initializing last_pos to \(0\), when not all types have appeared yet, the minimum value will be \(0\) and \(0\) will be added to the answer (meaning no valid interval exists for that right endpoint). This neatly avoids the need for explicit conditional branches.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> last_pos(8, 0);
    long long ans = 0;

    for (int r = 1; r <= n; ++r) {
        int c;
        cin >> c;
        last_pos[c] = r;

        int min_pos = r;
        for (int i = 1; i <= 7; ++i) {
            min_pos = min(min_pos, last_pos[i]);
        }
        ans += min_pos;
    }

    cout << ans << "\n";

    return 0;
}

This editorial was generated by gemini-3.8-flash-high.