Three Occurrences
Contest: Educational Codeforces Round 95 (Rated for Div. 2)
Difficulty rating: 2500
Tags: data structures, divide and conquer, hashing, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ integers. We denote the subarray $$$a[l..r]$$$ as the array $$$[a_l, a_{l + 1}, \dots, a_r]$$$ ($$$1 \le l \le r \le n$$$).

A subarray is considered good if every integer that occurs in this subarray occurs there exactly thrice. For example, the array $$$[1, 2, 2, 2, 1, 1, 2, 2, 2]$$$ has three good subarrays:

- $$$a[1..6] = [1, 2, 2, 2, 1, 1]$$$;
- $$$a[2..4] = [2, 2, 2]$$$;
- $$$a[7..9] = [2, 2, 2]$$$.

Calculate the number of good subarrays of the given array $$$a$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le n$$$).

Output format:
Print one integer — the number of good subarrays of the array $$$a$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
9
1 2 2 2 1 1 2 2 2

Example output:
3

Example input:
10
1 2 3 4 1 2 3 1 2 3

Example output:
0

Editorial:
Let's consider two solutions: a non-deterministic and a deterministic one.
The random solution goes like that.
Let's assign a random integer to each value from $$$1$$$ to $$$n$$$ (to value, not to a position). Let the value of the subarray be the trit-wise sum of the assigned integers of all values on it. Trit-wise is the analogue of bit-wise sum (xor) but in ternary system. So adding up the same integer three times trit-wise is always equal to zero. Thus, if the value on a subarray is zero then each value appears on it a multiple of three times. How to count the number of such subarrays? Process the array from left to right and store the prefix trit-wise sums in a map. The number of the valid subarrays that end in the current position is the number of occurrences of the current prefix trit-wise sum in a map. The current sum should be added to the map afterwards.
However, that's not what the problem asks us to find. Let's consider another problem: count the number of subarray such that each number appears no more than three times. This can be done with two pointers. Process the array from left to right and for each number store the positions it occurred on. If some number appears at least four times than the left pointer should be moved to the next position after the fourth-to-last position. The number of valid subarrays the end in the current position is the distance to the left pointer.
Let's combine these problems: maintain the pointer to only the valid positions and remove the prefix trit-wise sums from the map as you increase the pointer. That way the map will only store the valid sums, and they can be added to answer as they are.
Assume you use $$$K$$$ trits. I guess the probability of the collision is the same as two vectors (out of $$$n$$$) colliding in a $$$K$$$-dimensional space with their coordinates being from $$$0$$$ to $$$2$$$. That will be about $$$\frac{1}{2}$$$ when $$$n \approx \sqrt{3^K}$$$ (according to birthday paradox) — and way less if we increase $$$K$$$.
Overall complexity: $$$O(nK \log n)$$$.
The deterministic solution (a.k.a. the boring one) goes like that.
Let's again process the array from left to right. Let the current position be the right border of the segment. Each number makes some constraints on where the left border might be. More specifically, it's two possible segments: between its last occurrence and the current position and between its fourth-to-last occurrence and its third-to-last one. Let's actually invert these segments. Bad segments are from the beginning of the array to the fourth-to-last occurrence, then from the second-to-last occurrence to the last one. So the valid left borders are in such positions that are covered by zero bad segments.
Let's keep track of them in a segment tree. Add $$$1$$$ on the bad subarrays. Now you have to count the number of $$$0$$$ values in a segtree. That's a pretty common problem. As we know that no values can go below $$$0$$$, $$$0$$$ should be a minimum element on the segment. So we can store a pair of (minimum on segment, number of minimums on segment). At the end the second value is the number of zeros if the first value is zero.
Overall complexity: $$$O(n \log n)$$$.