这道题是 LeetCode 第 478 场周赛的 Q4，难度为困难。核心解法是判断区间合法性（同余）+ 中位数贪心 + 可持久化线段树查询区间第 k 小。
---
核心思路
1. 可行性判断（同余）：每次操作改变量为 k 的倍数，元素 mod k 的值不变。因此区间内所有元素必须模 k 同余，否则返回 -1。预处理差分数组可 O(1) 判断任意区间是否合法。
2. 最小操作次数（中位数贪心）：若所有元素可变为相等，让它们都变成区间的中位数时操作次数最少。设区间长度为 m，中位数为 v（第 (m+1)//2 小），前 x 小元素和为 s0，剩余元素和为 s1，则：
ans = (v * x - s0) // k + (s1 - v * (m - x)) // k
3. 数据结构（可持久化线段树/主席树）：需快速查询任意区间的第 k 小值及前 k 小元素之和。使用可持久化线段树（主席树），每个版本 root[i] 对应前缀 nums[0..i] 的权值线段树。
---
Python3 代码实现
```python
from typing import List
import bisect
class PersistentSegTree:
"""可持久化线段树（主席树），支持查询区间第k小及前k小和"""
def __init__(self, nums: List[int]):
# 离散化
self.vals = sorted(set(nums))
self.n = len(self.vals)
self.idx = {v: i + 1 for i, v in enumerate(self.vals)} # 1-based
# 动态开点数组
self.left = [0]
self.right = [0]
self.cnt = [0]
self.sum = [0]
# 构建版本树
self.roots = [0]
for num in nums:
self.roots.append(self._update(self.roots[-1], 1, self.n, self.idx[num], num))
def _update(self, prev: int, l: int, r: int, pos: int, val: int) -> int:
"""插入一个新节点，返回新节点下标"""
cur = len(self.cnt)
self.left.append(self.left[prev])
self.right.append(self.right[prev])
self.cnt.append(self.cnt[prev] + 1)
self.sum.append(self.sum[prev] + val)
if l != r:
mid = (l + r) // 2
if pos <= mid:
new_left = self._update(self.left[prev], l, mid, pos, val)
self.left[cur] = new_left
else:
new_right = self._update(self.right[prev], mid + 1, r, pos, val)
self.right[cur] = new_right
return cur
def _query_kth(self, u: int, v: int, l: int, r: int, k: int) -> int:
"""查询区间 [l, r] 的第 k 小值（返回离散化前的值）"""
if l == r:
return self.vals[l - 1]
mid = (l + r) // 2
left_count = self.cnt[self.left[v]] - self.cnt[self.left[u]]
if left_count >= k:
return self._query_kth(self.left[u], self.left[v], l, mid, k)
else:
return self._query_kth(self.right[u], self.right[v], mid + 1, r, k - left_count)
def _query_sum_le(self, u: int, v: int, l: int, r: int, limit: int) -> tuple:
"""查询区间内 <= limit 的元素个数和元素和，limit 为离散化下标"""
if l == r:
return self.cnt[v] - self.cnt[u], self.sum[v] - self.sum[u]
if r <= limit:
return self.cnt[v] - self.cnt[u], self.sum[v] - self.sum[u]
mid = (l + r) // 2
if limit <= mid:
return self._query_sum_le(self.left[u], self.left[v], l, mid, limit)
else:
lc, ls = self._query_sum_le(self.left[u], self.left[v], l, mid, limit)
rc, rs = self._query_sum_le(self.right[u], self.right[v], mid + 1, r, limit)
return lc + rc, ls + rs
def kth(self, l: int, r: int, k: int) -> int:
"""查询原数组区间 [l, r] 的第 k 小值（0-based）"""
return self._query_kth(self.roots[l], self.roots[r + 1], 1, self.n, k)
def sum_le(self, l: int, r: int, limit_val: int) -> tuple:
"""查询原数组区间 [l, r] 内 <= limit_val 的元素个数和元素和（0-based）"""
limit_idx = bisect.bisect_right(self.vals, limit_val)
if limit_idx == 0:
return 0, 0
return self._query_sum_le(self.roots[l], self.roots[r + 1], 1, self.n, limit_idx)
class Solution:
def minOperations(self, nums: List[int], k: int, queries: List[List[int]]) -> List[int]:
n = len(nums)
# 1. 预处理：判断区间内模k是否同余
# diff[i] = 1 表示 nums[i] 和 nums[i-1] 模k不同余
diff = [0] * n
for i in range(1, n):
diff[i] = diff[i - 1] + (0 if (nums[i] - nums[i - 1]) % k == 0 else 1)
# 2. 原数组前缀和
prefix_sum = [0] * (n + 1)
for i, num in enumerate(nums):
prefix_sum[i + 1] = prefix_sum[i] + num
# 3. 构建主席树
pst = PersistentSegTree(nums)
ans = []
for l, r in queries:
if l == r:
ans.append(0)
continue
# 判断区间内是否所有元素模k同余
if diff[r] - diff[l] != 0:
ans.append(-1)
continue
length = r - l + 1
x = (length + 1) // 2 # 中位数位置（第x小）
# 查询中位数的值
median = pst.kth(l, r, x)
# 查询前x小的元素个数和元素和（即 <= median 的部分）
cnt_le, sum_le = pst.sum_le(l, r, median)
# 剩余元素的和
sum_total = prefix_sum[r + 1] - prefix_sum[l]
sum_gt = sum_total - sum_le
# 计算操作次数
ops = (median * cnt_le - sum_le) // k + (sum_gt - median * (length - cnt_le)) // k
ans.append(ops)
return ans
```
---
复杂度分析
· 时间复杂度：预处理 O(n log n)，每个查询 O(log n)，总体 O((n + q) log n)
· 空间复杂度：O(n log n)
