题解：[ABC396F] Rotated Inversions

U•ェ•*U · 2025-03-10 22:20:02 · 题解

本文遵循 CC BY-NC-ND 4.0 协议，作者：U•ェ•*U，转载请获得作者授权。

先求 k=0 时的逆序数：用树状数组在 O(N\log M) 时间内统计标准逆序数。

分析 k\to k+1 时逆序数的变化： 观察每个位置 i ，当 k 增加 1 时，B_i = (A_i+k)\mod M 只有在等于模数（即 A_i+k = M-1）时变为 0，就改变了它在序列中的相对大小。可以证明，当某个位置 i 满足 k = M-1-A_i 时，该位置会改变贡献，对全局逆序数的影响为

因此可以令一个差分数组 diff（下标范围 [0,M-1]）满足：对于每个位置 i，在 k = M-1-A_i 时，加上 2\cdot i-(N-1) 。

最后，对于每个 k，我们加上 diff_k 即可。

import sys

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
tree = [0] * (200010)
diff = [0] * (200010)

def add(x, val):
    x += 1
    while x <= m:
        tree[x] += val
        x += (x & -x)

def query(x):
    x += 1
    res = 0
    while x:
        res += tree[x]
        x -= (x & -x)
    return res

def main():
    tmp = 0
    for i in range(n):
        tmp += i - query(a[i])
        add(a[i], 1)
        diff[m - 1 - a[i]] += (2 * i - (n - 1))

    print(tmp)
    for k in range(1, m):
        tmp += diff[k - 1]
        print(tmp)

if __name__ == '__main__':
    main()