結果
問題 | No.1300 Sum of Inversions |
ユーザー | eijirou |
提出日時 | 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 |
ソースコード
# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree# Fenwick Tree# 0-indexedclass BinaryIndexedTree:# a is virtual array# a = [0] * ndef __init__(self, n, mod):self.size = nself.data = [0] * (n+1)self.mod = mod# return sum(a[0:i] % mod)def query(self, i):res = 0while i > 0:res += self.data[i]res %= self.modi -= i & -ireturn res# a[i] += xdef add(self, i, x):i += 1while i <= self.size:self.data[i] += xself.data[i] %= self.modi += i & -idef debug(self):print([self.query(i+1)-self.query(i) for i in range(self.size)])mod = 998244353def main():n = int(input())a = list(map(int, input().split()))b = list(sorted(enumerate(a), key=lambda x: x[1]))a = [(0, 0)] * nfor 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 = 0for 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()