Official

H - サンドイッチな組/Sandwich triplet Editorial by sounansya


以下の条件を全て満たす \((i,j,k)\) の個数を \(X\) とします。

  • \(1\le i < j < k \le N\)
  • \(A_i= A_k\)

また、以下の条件を全て満たす \((i,j,k)\) の個数を \(Y\) とします。

  • \(1\le i < j < k \le N\)
  • \(A_i =A_j= A_k\)

すると、求める答えは \(X-Y\) として表すことができます。したがって、 \(X,Y\) の値がそれぞれ求まれば良いです。

\(c\) に対し \(A_i=c\) を満たす \(i\) を昇順に並べた整数列を \(B^c=(B^c_1,B^c_2,\ldots,B^c_{L_c})\) とします。

[1] \(X\) を求める方法

\(i,k\) を固定することで、 \(\displaystyle X=\sum_c \sum_{1\le i < k \le L_c} (B^c_k - B^c_i - 1)\) となります。

\(\displaystyle \sum_{1\le i < k \le L_c} (B^c_k - B^c_i - 1)=\sum_{i=1}^{L_c} (2i-L-1)B_i^c-\frac{L(L-1)}2\) となるので、各 \(B^c\) に対してこの式を計算することで全体として計算量 \(O(N)\) で求めることができます。

[2] \(Y\) を求める方法

\(Y\) は同じ要素の \(3\) つ組の個数なので、 \(\displaystyle Y=\sum_c \binom{L_c}3\) となります。

以上を適切に実装することでこの問題に正答することができます。計算量は \(B^c\) を求める部分がボトルネックとなり \(O(N \log N)\) です。

実装例(Python3)

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
s = defaultdict(lambda: [])
for i in range(n):
    s[a[i]].append(i)
x, y = 0, 0
for b in s.values():
    l = len(b)
    for i in range(l):
        x += (2 * i - l + 1) * b[i]
    x -= l * (l - 1) // 2
    y += l * (l - 1) * (l - 2) // 6
print(x - y)