Python 版题解
题目描述
给定已知序列,求排序后每个位置的交换次数
树状数组
时间复杂度
$O(log\ n)$
分析
其实思路和 1265. 数星星 差不多,统计每个数出现的次数。判断当前时刻,在该位置前有多少个数比它大,在该位置后有多少个数比它小。
Python 代码
import sys
n = int(input())
a = [0] + list(map(lambda x: int(x) + 1, sys.stdin.readline().strip().split()))
N = max(a)
tr = [0 for i in range(N+1)]
state = [0 for i in range(n+1)] # 记录每个位置的交换次数
def lowbit(x):
return x & -x
# 单点修改
def add(x, v):
i = x
while i <= N:
tr[i] += v
i += lowbit(i)
# 区间查询
def query(x):
res = 0
i = x
while i:
res += tr[i]
i -= lowbit(i)
return res
for i in range(1, n+1):
add(a[i], 1)
state[i] += query(N) - query(a[i]) # a[i] 前有多少个比它大
tr = [0 for i in range(N+1)]
# 逆序加入
while i:
add(a[i], 1)
state[i] += query(a[i] - 1) # a[i] 后有多少个比它小
i -= 1
print(int(sum(map(lambda x: 0.5*x*x+0.5*x, state))))
归并排序
时间复杂度
$O(log\ n)$
分析
利用归并排序中交换的操作,计算序列中每个数排序前后位置的变化,即可得出交换次数。
Python 代码
import sys
n = int(input())
q = list(map(int, sys.stdin.readline().strip().split()))
class Node():
def __init__(self):
self.val = 0 # 数值大小
self.mk = 0 # 交换次数
self.idx = 0 # 索引
f = [Node() for i in range(n)]
for i in range(n):
f[i].val = q[i]
f[i].idx = i
tmp = [Node() for i in range(n)]
def merge_sort(f, l, r):
if l >= r:
return
# 二分
mid = l + r >> 1
# 分治
merge_sort(f, l, mid), merge_sort(f, mid + 1, r)
# 合并
k = l
i = l
j = mid + 1
while i <= mid and j <= r:
if f[i].val <= f[j].val:
tmp[k].val = f[i].val
tmp[k].idx = f[i].idx
tmp[k].mk = f[i].mk
k += 1
i += 1
else:
tmp[k].val = f[j].val
tmp[k].idx = f[j].idx
tmp[k].mk = f[j].mk
k += 1
j += 1
# 合并剩余区间
while i <= mid:
tmp[k].val = f[i].val
tmp[k].idx = f[i].idx
tmp[k].mk = f[i].mk
k += 1
i += 1
while j <= r:
tmp[k].val = f[j].val
tmp[k].idx = f[j].idx
tmp[k].mk = f[j].mk
k += 1
j += 1
# 更新
for i in range(l, r + 1):
f[i].val = tmp[i].val
f[i].idx = i
f[i].mk = tmp[i].mk + abs(tmp[i].idx - i)
merge_sort(f, 0, n - 1)
res = 0
for i in range(n):
res += f[i].mk * (f[i].mk + 1) / 2
print(int(res))