結果

問題 No.1300 Sum of Inversions
ユーザー eijiroueijirou
提出日時 2020-11-27 22:12:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,058 ms / 2,000 ms
コード長 1,373 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 134,152 KB
最終ジャッジ日時 2024-07-26 13:08:07
合計ジャッジ時間 26,771 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
# Fenwick Tree
# 0-indexed
class BinaryIndexedTree:
    # a is virtual array
    # a = [0] * n
    def __init__(self, n, mod):
        self.size = n
        self.data = [0] * (n+1)
        self.mod = mod

    # return sum(a[0:i] % mod)
    def query(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            res %= self.mod
            i -= i & -i
        return res

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            self.data[i] %= self.mod
            i += i & -i

    def debug(self):
        print([self.query(i+1)-self.query(i) for i in range(self.size)])

mod = 998244353

def main():
    n = int(input())
    a = list(map(int, input().split()))

    b = list(sorted(enumerate(a), key=lambda x: x[1]))
    a = [(0, 0)] * n
    for i in range(n):
        a[b[i][0]] = (i, b[i][1])

    s1 = BinaryIndexedTree(n, mod)
    cnt1 = BinaryIndexedTree(n, mod)
    s2 = BinaryIndexedTree(n, mod)
    cnt2 = BinaryIndexedTree(n, mod)
    ans = 0
    for i, x in a[::-1]:
        ans += cnt2.query(i)*x+s2.query(i)
        s2.add(i, cnt1.query(i)*x+s1.query(i))
        cnt2.add(i, cnt1.query(i))
        s1.add(i, x)
        cnt1.add(i, 1)

    print(ans % mod)

main()
0