結果

問題 No.1300 Sum of Inversions
ユーザー lam6er
提出日時 2025-03-20 21:20:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 585 ms / 2,000 ms
コード長 2,488 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 186,156 KB
最終ジャッジ日時 2025-03-20 21:22:18
合計ジャッジ時間 16,726 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing

    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] = (self.tree[idx] + delta) % MOD
            idx += idx & -idx

    def query(self, idx):
        res = 0
        while idx > 0:
            res = (res + self.tree[idx]) % MOD
            idx -= idx & -idx
        return res

def compress_coordinates(arr):
    unique = sorted(set(arr))
    rank = {v:i+1 for i, v in enumerate(unique)}  # 1-based
    compressed = [rank[x] for x in arr]
    return compressed, len(unique)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    if N < 3:
        print(0)
        return

    compressed_rank, max_rank = compress_coordinates(A)

    right = [0] * N
    ft_right = FenwickTree(max_rank)
    for j in range(N-1, -1, -1):
        cr = compressed_rank[j]
        count = ft_right.query(cr - 1)
        right[j] = count % MOD
        ft_right.update(cr, 1)

    sum_pairs = [0] * N
    ft_sum_pairs = FenwickTree(max_rank)
    for i in range(N-1, -1, -1):
        cr = compressed_rank[i]
        sum_p = ft_sum_pairs.query(cr - 1)
        sum_pairs[i] = sum_p % MOD
        ft_sum_pairs.update(cr, right[i] % MOD)

    sum_part1 = 0
    for i in range(N):
        sum_part1 = (sum_part1 + sum_pairs[i] * A[i]) % MOD

    left = [0] * N
    ft_left = FenwickTree(max_rank)
    for j in range(N):
        cr = compressed_rank[j]
        count_so_far = j
        cnt_le = ft_left.query(cr)
        left_j = (count_so_far - cnt_le) % MOD
        left[j] = left_j
        ft_left.update(cr, 1)

    sum_part2 = 0
    for j in range(N):
        l = left[j] % MOD
        r = right[j] % MOD
        contrib = (l * r) % MOD
        contrib = (contrib * A[j]) % MOD
        sum_part2 = (sum_part2 + contrib) % MOD

    sum_part3 = 0
    sum_left_total = 0
    ft_part3 = FenwickTree(max_rank)
    for k in range(N):
        cr = compressed_rank[k]
        sum_le = ft_part3.query(cr)
        sum_gr = (sum_left_total - sum_le) % MOD
        sum_part3 = (sum_part3 + sum_gr * A[k]) % MOD
        sum_left_total = (sum_left_total + left[k]) % MOD
        ft_part3.update(cr, left[k] % MOD)

    total = (sum_part1 + sum_part2 + sum_part3) % MOD
    print(total)

if __name__ == "__main__":
    main()
0