Summary

Given a sequence \(C\) of length \(N\) (where each element is between \(1\) and \(7\), inclusive), this problem asks us to count the number of pairs \((l, r)\) such that all values from \(1\) to \(7\) appear in the subsegment \([l, r]\). This is a classic two-pointer problem.

Analysis

Naive Approach

Checking all pairs \((l, r)\) would take \(O(N^2)\) time. For \(N \le 10^6\), there are around \(10^{12}\) pairs, which will clearly result in TLE. Counting the distinct values for each interval would be even slower.

Key Observation 1: Monotonicity

When extending the interval to the right (increasing \(r\)), the set of distinct stamp types contained in it only grows and never decreases. Similarly, extending the interval to the left (decreasing \(l\)) only adds types.

Therefore, for a fixed \(r\): - If \([l, r]\) satisfies the condition (contains all \(7\) types), then for any \(l' \le l\), \([l', r]\) also satisfies the condition.

This means that the set of valid left endpoints \(l\) forms a prefix of the form \(1, 2, \dots, f(r)\) (where \(f(r)\) is the maximum \(l\) that satisfies the condition, or \(f(r) = 0\) if no such \(l\) exists).

Thus, the answer can be written as: $\(\text{ans} = \sum_{r=1}^{N} f(r)\)\( All that remains is to compute \)f®\( efficiently for each \)r$.

Key Observation 2: Monotonicity of \(f(r)\)

As \(r\) increases, the condition becomes more relaxed, so \(f(r)\) is monotonically non-decreasing (\(f(1) \le f(2) \le \dots \le f(N)\)). Consequently, there is no need to rewind the left endpoint \(l\); we can compute \(f(r)\) for all \(r\) simply by moving \(l\) in one direction. This is the two-pointer technique.

Concrete example: When \(C = (1, 1, 2, 3, 4, 5, 6, 7)\): - Up to \(r = 7\), the value \(7\) has not appeared yet, so \(f(r) = 0\). - For \(r = 8\): the interval \([2, 8]\) contains all types, whereas \([3, 8]\) does not contain \(1\), so \(f(8) = 2\).

Therefore, the answer is \(2\) (the pairs \((1,8)\) and \((2,8)\)).

Algorithm

We maintain the frequency of each type in the window \([l, r]\) as cnt[1..7], along with the number of distinct types present, distinct.

For \(r = 1, 2, \dots, N\) in order, perform the following:

1. Add \(C_r\) to the window. If cnt[C_r] == 0 before adding, increment distinct by \(1\).
2. Shrink the left end of the window as much as possible without changing the set of types present: While cnt[C_l] > 1, decrement cnt[C_l]-- and increment l++.
   • When the loop ends, cnt[C_l] == 1, meaning the element at the left end is the only occurrence in the window. Shrinking any further would reduce the number of types by \(1\), so \(l\) represents the “maximum left endpoint that preserves the set of types.”
   • Because this shrinking operation never reduces the number of types, once distinct reaches \(7\), it will remain \(7\).
3. If distinct == 7, this \(l\) is precisely \(f(r)\), so add ans += l (there are \(l\) choices for the left endpoint: \(1, 2, \dots, l\)).

The key idea is that instead of checking whether distinct == 7 to advance \(l\), we always maintain the maximum \(l\) that preserves the set of types. This keeps the conditional logic simple.

(Alternatively, one can maintain \(\mathrm{last}[v]\), the last occurrence of each type \(v\) up to \(r\), and compute \(f(r) = \min_{v=1}^{7} \mathrm{last}[v]\) (or \(0\) if any type has not appeared). Since there are only \(7\) types, taking the minimum each time runs in \(O(7N)\), which is also fast enough.)

Complexity

• Time Complexity: \(O(N)\) (Since \(l\) only increases monotonically overall, the inner while loop runs at most \(N\) times in total.)
• Space Complexity: \(O(N)\) (To store the sequence. If \(C\) is processed while reading the input, \(O(1)\) auxiliary space is also possible.)

Implementation Notes

• Integer Overflow: The answer can be up to \(O(N^2)\), specifically around \(10^{12}\), which will overflow a \(32\)-bit signed integer. Use a 64-bit integer (long long) and cast appropriately, such as ans += (long long)l; (this does not need to be considered in Python).

• Fast I/O: Since \(N \le 10^6\), the input size is relatively large. In C++, use scanf, or if using cin, do not forget ios::sync_with_stdio(false); cin.tie(nullptr);.

• Indexing: Since cnt tracks types \(1\) through \(7\), it is convenient to use an array of size \(8\) and leave index \(0\) unused.

• While Loop Condition: It is safer to include l <= r in the loop condition (in practice, it will stop at cnt[C_l] == 1 before the window becomes empty, but making the boundary explicit provides peace of mind).

• If all \(7\) types never appear together, distinct will never reach \(7\) and ans will remain \(0\), which handles that case correctly.

  Source Code

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

int main(){
    int n;
    if(scanf("%d",&n)!=1) return 0;
    vector<int> c(n+1);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    long long ans=0;
    int cnt[8]={0};
    int distinct=0;
    int l=1;
    for(int r=1;r<=n;r++){
        if(cnt[c[r]]++==0) distinct++;
        while(l<=r && cnt[c[l]]>1){
            cnt[c[l]]--;
            l++;
        }
        if(distinct==7) ans += (long long)l;
    }
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.