Submission #39047193

---

Source Code Expand

from collections import defaultdict
N = int(input())

AL = list(map(int, input().split()))

# 全部違う数字の場合のコスト
cost = 0
for m in range(1, N+1):
    cost += (N-m+1) * (m // 2)

num_poss = defaultdict(list)
for i, val in enumerate(AL):
    num_poss[val].append(i)

def binsearch(vec, key):
    ng = -1
    ok = len(vec)
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        # key未満である要素のうち一番左
        if vec[mid] < key:
            ok = mid
        else:
            ng = mid
    return ok

for val, poss in num_poss.items():
    if len(poss) < 2:
        continue
    poss1 = [v+1 for v in poss]
    poss2 = [N-v for v in poss]
    cumsum = [poss2[0]]
    for i in range(1, len(poss2)):
        cumsum.append(cumsum[i-1]+poss2[i])
    pl = len(poss)
    for i in range(pl-1):
        # # poss2[i+1:]のうちposs1[i]より小さいものはその区間の和、小さいものはposs1[i]*区間サイズ
        found = binsearch(poss2, poss1[i])
        found = max(found, i+1)
        if found < len(cumsum):
            cost -= (cumsum[-1] - cumsum[found-1])
        cost -= poss1[i] * (found - 1 - i)
        # for j in range(i+1, pl):
        #    # i, j ペアを含む部分列の個数だけコストが減る
        #    cost -= min(poss1[i], poss2[j])

print(cost)

"""
ナイーブにやると
部分列が先頭と末尾N通りずつでN^2こある
それぞれの列について、先頭と末尾から見ていって不一致の個数だけ変更が必要。コストN
トータルN^3で遅すぎ

中心1個決める（数値がある個所とする）
1個の時コスト0
1+2iこの時コストx
両方向に1個ずつ視野を広げて、一致するかどうかみる。
1+2(i+1)個の範囲になる
一致するならコストx、一致しないならコストx+1
xの累積和を求める
中心1個に対して計算量Nになる
中心はN通り程度
N^2コストでまだ駄目

もし全部の数字が違ったら、部分列ごとにその長さ/2程度がコストになる
2つの数字が同じ場合、そのペアを含む全部分列のコストが1減る。部分列の個数は定数時間
3個以上の数字が同じ場合、全ペアに対して全部分列のコストが1減る。N個の場合N^2ペアあるが速度的にどうだろうか

正確に計算。長さN

"""

Submission Info

Judge Result