問題概要

Indeedなう（予選B）D - 高橋くんと数列
$1$以上$C$以下の整数$k$について、$k$が含まれる部分列の個数をそれぞれ求める

公式解説概要

全ての部分列の個数から、$k$を含まない部分列の個数を引く

自分の解法

$1$以上$N$以下の$i$について、$A_i$を含んだ部分列の内、$A_i$より前にある同じ整数を含まない部分列の個数を数える(後ろに同じ整数があった場合、含んでも良い)。
$1$以上$C$以下の整数について、最後にそれが表れた場所を記録することで、公式解説と同じ$O(N+C)$で解ける。

自分の解答

N, C = map(int, input().split())
A = list(map(int, input().split()))

ans = [0]*C
pr = [-1]*C

for i in range(N):
    a = A[i]-1
    ans[a] += (i-pr[a]) * (N-i)
    pr[a] = i

for a in ans:
    print(a)

雑な図解

入力例1

線の長さが部分列の範囲、色がどの整数を含んだ部分列か(赤は$1$、青は$2$)を表しています。

感想

大きい値を求めるのがなんとなく嫌なのでこっちの方が好き