結果

問題 No.2938 Sigma Sigma Distance Distance Problem
コンテスト
ユーザー AP25
提出日時 2026-06-07 14:31:19
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 1,626 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 418 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 69,760 KB
最終ジャッジ日時 2026-06-07 14:31:22
合計ジャッジ時間 3,778 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# for evil case
# i,jの0,1-indexは差分なので意識せず良い
# i<jのケースをカウントして２倍する
# Ai < Aj / Ai > Ajのケースに分けて式展開
# 展開した各項をAiを添え字としたFenwickTreeで管理

import typing


class FenwickTree:
    '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree'''

    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.data = [0] * n

    def add(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        return self._sum(right) - self._sum(left)

    def _sum(self, r: int) -> typing.Any:
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r

        return s

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

ans = 0
ft_i = FenwickTree(502)
ft_Ai = FenwickTree(502)
ft_iAi = FenwickTree(502)
ft_cnt = FenwickTree(502)

ans = 0
for j in range(N):
    # A[i] < A[j]
    ans += j *A[j] * ft_cnt.sum(0,A[j])
    ans -= j * ft_Ai.sum(0,A[j])
    ans -= A[j] * ft_i.sum(0,A[j])
    ans += ft_iAi.sum(0, A[j])
    # A[i] > A[j]
    ans -= j * A[j] * ft_cnt.sum(A[j]+1, 501)
    ans += j * ft_Ai.sum(A[j]+1,501)
    ans += A[j] * ft_i.sum(A[j]+1,501)
    ans -= ft_iAi.sum(A[j]+1,501)

    ft_i.add(A[j],j)
    ft_Ai.add(A[j],A[j])
    ft_iAi.add(A[j],j*A[j])
    ft_cnt.add(A[j],1)

print(ans*2)
0