这道题是 LeetCode 第 478 场周赛的 Q4难度为困难。核心解法是判断区间合法性同余 中位数贪心 可持久化线段树查询区间第 k 小。---核心思路1. 可行性判断同余每次操作改变量为 k 的倍数元素 mod k 的值不变。因此区间内所有元素必须模 k 同余否则返回 -1。预处理差分数组可 O(1) 判断任意区间是否合法。2. 最小操作次数中位数贪心若所有元素可变为相等让它们都变成区间的中位数时操作次数最少。设区间长度为 m中位数为 v第 (m1)//2 小前 x 小元素和为 s0剩余元素和为 s1则ans (v * x - s0) // k (s1 - v * (m - x)) // k3. 数据结构可持久化线段树/主席树需快速查询任意区间的第 k 小值及前 k 小元素之和。使用可持久化线段树主席树每个版本 root[i] 对应前缀 nums[0..i] 的权值线段树。---Python3 代码实现pythonfrom typing import Listimport bisectclass 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) // 2if pos mid:new_left self._update(self.left[prev], l, mid, pos, val)self.left[cur] new_leftelse:new_right self._update(self.right[prev], mid 1, r, pos, val)self.right[cur] new_rightreturn curdef _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) // 2left_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) // 2if 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 rsdef kth(self, l: int, r: int, k: int) - int:查询原数组区间 [l, r] 的第 k 小值0-basedreturn 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-basedlimit_idx bisect.bisect_right(self.vals, limit_val)if limit_idx 0:return 0, 0return 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] * nfor 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)continuelength r - l 1x (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)) // kans.append(ops)return ans---复杂度分析· 时间复杂度预处理 O(n log n)每个查询 O(log n)总体 O((n q) log n)· 空间复杂度O(n log n)