Overview

Given a sequence \(C\) of length \(N\) (where each element is between \(1\) and \(7\)), this problem asks us to count the number of contiguous subarrays \((l, r)\) that contain all values from \(1\) to \(7\). If we notice that we can easily find the “number of valid \(l\)” when the right endpoint \(r\) is fixed, we can solve this problem in \(O(N)\).

Analysis

Naive Approach

The first idea that comes to mind is to try all pairs \((l, r)\) and check whether all \(7\) types are present in that interval. However, the number of pairs \((l, r)\) is about \(N^2/2 \approx 5 \times 10^{11}\) (when \(N = 10^6\)), which is far too large to pass within the time limit.

Key Observation 1: Monotonicity

When an interval \([l, r]\) satisfies the condition, the condition continues to hold even if we decrease \(l\) further (expanding the interval to the left). Since expanding the interval only adds to the set of included stamps, the property of containing \(\{1,\dots,7\}\) is preserved.

Therefore, for a fixed right endpoint \(r\), the valid values of \(l\) form a contiguous range of the form:

\[1 \le l \le L(r)\]

(where \(L(r)\) is the maximum valid \(l\), or \(0\) if no such \(l\) exists). That is, the number of valid pairs for a fixed right endpoint \(r\) is exactly \(L(r)\).

Key Observation 2: What \(L(r)\) Really Is

Let \(\mathrm{last}[k]\) be the most recent position where type \(k\) appeared at or before \(r\). The condition for the interval \([l, r]\) to contain type \(k\) is:

\[l \le \mathrm{last}[k]\]

(if type \(k\) has not appeared yet, \(\mathrm{last}[k]\) does not exist and it can never be included). Since this must hold for all \(k = 1, \dots, 7\), we have:

\[L(r) = \min_{1 \le k \le 7} \mathrm{last}[k]\]

If we initialize \(\mathrm{last}[k]\) to \(0\) for types that have not yet appeared, a minimum value of \(0\) naturally handles the case “not all 7 types have appeared yet \(\to\) 0 valid intervals,” which is very convenient.

Note that since \(C_i \in \{1,\dots,7\}\), “containing all \(7\) types” is equivalent to “the set of elements equals \(\{1,\dots,7\}\)” (we don’t need to worry about extraneous values).

Concrete Example

For \(N = 8\) and \(C = (1,2,3,4,5,6,7,1)\):

• \(r = 1 \dots 6\): Not all 7 types have appeared yet (some \(\mathrm{last}\) is \(0\)) \(\to\) \(0\) pairs
• \(r = 7\): \(\mathrm{last} = (1,2,3,4,5,6,7)\), minimum is \(1\) \(\to\) \(1\) pair (\((1,7)\))
• \(r = 8\): \(\mathrm{last}[1]\) is updated to \(8\), giving \(\mathrm{last} = (8,2,3,4,5,6,7)\), minimum is \(2\) \(\to\) \(2\) pairs (\((1,8), (2,8)\))

The total is \(3\) pairs, which matches the valid subarrays \((1,7), (1,8), (2,8)\).

Algorithm

1. Initialize an array last of length \(8\) with \(0\) (using indices \(1\) through \(7\)).
2. For each \(i = 1, 2, \dots, N\) in order:
   • Update last[C_i] = i.
   • Compute \(m = \min(\mathrm{last}[1], \dots, \mathrm{last}[7])\).
   • Add \(m\) to the answer (if \(m = 0\), it adds nothing).
3. Output the total.

This problem can also be solved with the same time complexity using the two-pointer technique by maintaining the occurrence count of each type while advancing the left pointer. However, since the number of types is small (at most \(7\)), recomputing the “minimum of the last occurrence positions” at each step as described above is simpler.

Complexity

• Time complexity: \(O(7N) = O(N)\)
• Space complexity: \(O(1)\) (excluding input storage; only a constant-sized array last is used)

Implementation Details

• Magnitude of the answer: The answer can be up to \(O(N^2)\) (on the order of \(5 \times 10^{11}\)), so in languages like C++, you must use long long. In Python, integers have arbitrary precision, so this is not an issue.

• Fast I/O: Since \(N \le 10^6\), in Python it is recommended to read the entire input at once using sys.stdin.buffer.read().split() instead of repeatedly calling input(). Furthermore, instead of converting all elements into a list of ints upfront, converting each element on the fly with int(data[i]) inside the loop saves both memory and time.

• Avoiding calls to min(): Calling min(last[1:8]) on \(7\) elements in each iteration incurs slicing and function call overhead \(10^6\) times. Unrolling the comparisons manually as shown in the code makes it run sufficiently fast even in Python.

• Representing unvisited types with \(0\): By initializing last with \(0\), we can minimize branching by naturally handling “not all 7 types have appeared yet \(\to\) minimum is \(0\) \(\to\) add nothing” (this works cleanly because the positions are \(1\)-indexed).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    last = [0] * 8
    ans = 0
    for i in range(1, n + 1):
        last[int(data[i])] = i
        m = last[1]
        t = last[2]
        if t < m: m = t
        t = last[3]
        if t < m: m = t
        t = last[4]
        if t < m: m = t
        t = last[5]
        if t < m: m = t
        t = last[6]
        if t < m: m = t
        t = last[7]
        if t < m: m = t
        if m:
            ans += m
    sys.stdout.write(str(ans) + "\n")

main()

---

This editorial was generated by claude5opus-high.