問題概要
$n$ 項からなる整数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．関数 $f \mathpunct{:} \{ 1, 2, \dots, n \}^2 \rightarrow \mathbb Z_{ \geq 0 }$ を以下で定義する：
\begin{align*}
f( l, r ) &= \langle A_l, A_{ l + 1 }, \dots, A_r \rangle \text{ に含まれる値の種類数} \\
&= \left| \{ A_l, A_{ l + 1 }, \dots, A_r \} \right|
\end{align*}
以下を求めよ：
\begin{equation*}
\sum_{ i = 1 }^n \sum_{ j = i }^n f( i, j )
\end{equation*}
制約
- $1 \leq n \leq 2 \times 10^5$
- $1 \leq A_i \leq n$
解法
$\sum \sum$ を平易に読めば，「$A$ のすべての連続部分列について，それに含まれる要素の種類数を求めた和」です．（式を見たままですが）対象となる部分列は $\Theta( n^2 )$ 個あることから，連続部分列をひとつずつ調べるような解法は TLE するので工夫が必要です．
$f( l, r )$ について「種類数」と一言で済ませているところを言い換えると，整数の内で $A[ l, r ]$ に含まれているものを数えているとも言えます．この気持ちで式にすると $\left| \{ x \mid x \in \mathbb Z, l \in \{ 1, 2, \dots, n \}, r \in \{ 1, 2, \dots, n \}, x \in A[ l, r ] \} \right|$*1 でしょうか．このように $x$ を先に固定すれば，$x$ を含む連続部分列の個数分だけ答えに $1$ ずつ寄与していることが分かります．これをすべての $x$ について計算し，和をとったものが問題の答えです．
では，各 $x \in A$*2についてその寄与を計算する方法を考えます．今回は，直接数える代わりに「余事象」に着目します．すなわち，$x$ を含まない連続部分列の個数を数え，すべての連続部分列の個数から引くことで欲しい値を求めます．
要素数 $w$ の列のすべての連続部分列の個数について考えます．問題文で言うような $l, r$ の取り方を数えてもよいのですが，この場合，
- $l = r$ であるようなものが $w$ 通り
- $l \neq r$ であるようなものが $\frac { w ( w - 1 ) } 2$ 通り
となってやや煩雑です．ここで見方を変えて，各要素の間（先頭の手前・末尾の後ろを含む）に「仕切り」があると考えます．こうすると，$w + 1$ 個の仕切りから異なる $2$ 個を選ぶことになるので，
\begin{equation*}
\frac { ( w + 1 ) w } 2
\end{equation*}
という一本の式になります．$w = n$ とすれば上記のすべての連続部分列の個数が求まります．
これは固定した $x$ を含まない列の数え上げにも応用できます．$x$ の出現位置（添字）を集めたものに $0, n + 1$ を加えてソートしたものを $I$ とします．このとき，各 $i \in \{ 1, 2, \dots, |I| - 1 \}$ に $x$ を含まない極大な連続部分列 $A[ I_i + 1, I_{ i + 1 } - 1 ]$ が $1$ : $1$ 対応して，それぞれの長さは $I_{ i + 1 } - I_i - 1$ となります．よって，$w = I_{ i + 1 } - I_i - 1$ として先程の議論を適用すれば，$x$ を含まない連続部分列の個数が求まります．
以上で必要な値の計算方法が分かったので，答えを求めることができます．計算量については，添字を $A$ の値ごとに分類してからそれぞれのリストを走査しているので，各添字は高々定数回だけ参照されることになります．よって，このアルゴリズムは $\Theta( n )$ 時間で動作します．
コード
LL solve( const int N, const VI occurences ) { LL res = LL( N ) * ( N + 1 ) / 2; REP( i, SZ( occurences ) - 1 ) { const int w = occurences[ i + 1 ] - occurences[i] - 1; res -= LL( w ) * ( w + 1 ) / 2; } return res; } int main() { IN( int, N ); VI A( N ); cin >> A; MAP_PRED( A ); VVI occurences( N ); for_each( ALL( occurences ), []( VI &row ){ row.PB( -1 ); } ); REP( i, N ) { occurences[ A[i] ].PB( i ); } for_each( ALL( occurences ), [&]( VI &row ){ row.PB( N ); } ); LL res = 0; REP( i, N ) { res += solve( N, occurences[i] ); } cout << res << endl; return 0; }
main = do n <- readInt as <- readInts print $ sum $ map ( solve n ) $ classify as classify as = elems $ runSTArray $ do lists <- newArray ( 1, n ) [ n + 1 ] forM_ ( reverse $ zip [ 1 .. ] as ) $ \( i, a ) -> do modifyArray lists a ( i : ) forM_ [ 1 .. n ] $ \a -> do modifyArray lists a ( 0 : ) return lists where n = length as solve n is = f n - ( sum $ map ( f . pred ) $ zipWith (-) ( tail is ) is ) where f w = w * ( w + 1 ) `div` 2
