按值排序找每个位置的最近值邻居，把好配对转成二维点并离线 Fenwick 查询。
OJ: luogu
题目 ID: P5677
难度:省选/NOI-
标签:离线查询树状数组最近邻python
日期: 2026-07-16 21:00
题意
有序对 (x,y) 在 a[y] 是 a[x] 的全局最近值时为好配对。询问下标区间内包含多少好配对，并按询问编号加权。
思路
数值互异。按值排序后，某个数的最近值只可能是相邻的前驱或后继；距离相等时两者都算。因此有序好配对总数至多 2n。
把每个有序对变成点 (max(x,y), min(x,y))。查询 [l,r] 要求第一坐标不超过 r 且第二坐标不小于 l。按查询右端排序，逐步把第一坐标合格的点加入 Fenwick；已加入总数减去第二坐标小于 l 的前缀数就是答案。
Python 知识
sorted(range(n), key=values.__getitem__)得到按值排列的原下标。key=lambda query: query[1]明确按右端点离线排序。- 重复二维点不能去重，因为相反方向是两组有序配对。
代码
python
import sys
data = iter(map(int, sys.stdin.buffer.read().split()))
n, query_count = next(data), next(data)
values = [next(data) for _ in range(n)]
ordered = sorted(range(n), key=values.__getitem__)
pairs = []
for position, index in enumerate(ordered):
left_gap = values[index] - values[ordered[position - 1]] if position else 10**30
right_gap = values[ordered[position + 1]] - values[index] if position + 1 < n else 10**30
if left_gap <= right_gap:
other = ordered[position - 1]
pairs.append((max(index, other), min(index, other)))
if right_gap <= left_gap:
other = ordered[position + 1]
pairs.append((max(index, other), min(index, other)))
queries = sorted(((next(data) - 1, next(data) - 1, identity + 1)
for identity in range(query_count)), key=lambda query: query[1])
pairs.sort()
tree = [0] * (n + 1)
def add(index):
index += 1
while index <= n:
tree[index] += 1
index += index & -index
def prefix(end):
result = 0
while end:
result += tree[end]
end -= end & -end
return result
pointer = 0
answer = 0
for left, right, identity in queries:
while pointer < len(pairs) and pairs[pointer][0] <= right:
add(pairs[pointer][1])
pointer += 1
answer += (pointer - prefix(left)) * identity
print(answer)复杂度
排序
总结
先证明好配对稀疏，再把“两个下标都在区间”转成二维偏序，是本题关键。