Overview

We want to find the number of contiguous intervals containing all \(7\) types of stamps. By fixing the right endpoint of the interval, we can count the number of valid left endpoints using the last occurrence of each stamp type.

Analysis

Checking All Intervals Is Too Slow

There are \(\frac{N(N+1)}{2}\) candidate intervals \((l,r)\) in total. Even if we maintain the set of stamp types while extending the right endpoint for each left endpoint, the time complexity is \(O(N^2)\).

Since \(N\) is up to \(10^6\), checking each interval one by one will not run in time.

Fixing the Right Endpoint and Considering the “Last Occurrence” of Each Type

Let us fix the right endpoint \(r\). Among checkpoints \(1\) through \(r\), let \(\mathrm{last}[s]\) be the position where stamp type \(s\) last appeared. For types that have not yet appeared, let \(\mathrm{last}[s]=0\).

The condition for the interval \([l,r]\) to contain stamp type \(s\) is as follows:

\(l \le \mathrm{last}[s]\)

Indeed, if the last occurrence is at or after \(l\), that position lies within the interval. Conversely, if that position is before \(l\), stamp type \(s\) does not appear in the interval.

Therefore, the necessary and sufficient condition for all \(7\) types to be included is:

\(l \le \min(\mathrm{last}[1],\mathrm{last}[2],\dots,\mathrm{last}[7])\)

Let this minimum value be \(m\). The valid left endpoints are \(1,2,\dots,m\), which gives exactly \(m\) valid left endpoints.

If there is any stamp type that has not yet appeared, \(m=0\), which naturally captures the fact that there are no valid intervals.

Concrete Example

Suppose the sequence of stamps is as follows:

\(1,2,3,4,5,6,7,1\)

When the right endpoint is \(r=7\), the last occurrences of each type are:

\((1,2,3,4,5,6,7)\)

The minimum value is \(1\), so there is \(1\) valid interval: \([1,7]\).

When the right endpoint moves to \(r=8\), only the last occurrence of type \(1\) is updated:

\((8,2,3,4,5,6,7)\)

The minimum value is now \(2\), so there are \(2\) valid intervals: \([1,8]\) and \([2,8]\).

By summing up these counts across all right endpoints, we can count all valid intervals without duplicates.

Algorithm

1. Initialize an array last to all \(0\)s, which tracks the last occurrence of each type.
2. Initialize the answer variable answer to \(0\).
3. Iterate the right endpoint \(r\) from \(1\) to \(N\), performing the following steps:
   • Read the stamp type \(C_r\).
   • Update the last occurrence of type \(C_r\) to \(r\).
   • Add the minimum value in last to answer.
4. Output answer.

For each right endpoint, the exact number of valid left endpoints is added. Since each interval has a unique right endpoint, there are no omissions or duplicate counts.

Complexity

• Time Complexity: \(O(7N)=O(N)\)
  At each checkpoint, we find the minimum element in an array of length \(7\).
• Space Complexity: \(O(7)=O(1)\)
  We only keep track of the last occurrence of each type, so there is no need to store the entire input sequence.

Implementation Notes

• Use 1-based indexing for checkpoint positions.
  This allows using the initial value of \(0\) to indicate “has not appeared yet”. array<int, 7> last{}; initializes all elements to \(0\).

• Map stamp types to array indices.
  Since the types are from \(1\) to \(7\) and array indices are from \(0\) to \(6\), type c is updated with last[c - 1] = r;.

• Update the last occurrence before adding the minimum value.
  This ensures that the stamp at the right endpoint \(r\) is included when counting the intervals.

• Use a 64-bit integer type for the answer.
  The total number of intervals can be up to \(\frac{N(N+1)}{2}\), which may not fit in a 32-bit integer. The provided code uses long long.

  Source Code

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    array<int, 7> last{};
    long long answer = 0;

    for (int r = 1; r <= N; ++r) {
        int c;
        cin >> c;
        last[c - 1] = r;
        answer += *min_element(last.begin(), last.end());
    }

    cout << answer << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.