题解：[ABC396F] Rotated Inversions

本文遵循 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

时，该位置会改变贡献，对全局逆序数的影响为

( \text{在该位置前的个数} ) - ( \text{在该位置后的个数} ) = 2\cdot i - (N-1)

因此可以令一个差分数组

diff

（下标范围

[0,M-1]

）满足：对于每个位置

i

，在

k = M-1-A_i

时，加上

2\cdot i-(N-1)

。

最后，对于每个

k

，我们加上

diff_k

即可。

PYTHON

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()

题解：[ABC396F] Rotated Inversions

文章操作

相关推荐

评论

题解：[ABC396F] Rotated Inversions