这道题是第 478 场周赛 Q4难度为困难核心是判断区间合法性 中位数贪心 可持久化线段树查询区间第 k 小。---题目概述给定数组 nums 和整数 k每次操作可将任意元素增加或减少 k。对每个查询 [l, r]求让子数组所有元素相等的最小操作次数若无法实现则返回 -1。---解题思路1. 判断可行性同余每次操作改变量为 k 的倍数元素 mod k 的值不变。因此区间内所有元素必须模 k 同余否则返回 -1。实现上预处理差分数组 diff[i] (nums[i] - nums[i-1]) % k 0 ? 0 : 1前缀和 cnt 可 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] 的权值线段树支持区间查询。---Java 代码实现javaclass Solution {public long[] minOperations(int[] nums, int k, int[][] queries) {int n nums.length, q queries.length;// 1. 合法性判断前缀和记录相邻差不是k倍数的位置int[] cnt new int[n];for (int i 1; i n; i) {cnt[i] cnt[i - 1] ((nums[i] - nums[i - 1]) % k 0 ? 0 : 1);}// 2. 原数组前缀和用于后续计算区间总和long[] sum new long[n 1];for (int i 0; i n; i) {sum[i 1] sum[i] nums[i];}// 3. 可持久化线段树SegTree tree new SegTree(nums);long[] ans new long[q];for (int i 0; i q; i) {int l queries[i][0], r queries[i][1];if (l r) {ans[i] 0;continue;}// 区间内存在模k不同余的元素无法实现if (cnt[r] - cnt[l] ! 0) {ans[i] -1;continue;}int m r - l 1;int x (m 1) / 2; // 中位数位置第x小long v tree.smallK(l, r, x); // 中位数的值long s0 tree.smallKSum(l, r, x); // 前x小的和long s1 sum[r 1] - sum[l] - s0; // 剩余元素的和ans[i] (v * x - s0) / k (s1 - v * (m - x)) / k;}return ans;}}class SegTree {private int[] root, lc, rc, cnt;private long[] sum;private int[] val;private int N, no;public SegTree(int[] a) {int n a.length;// 离散化val a.clone();Arrays.sort(val);N 1;for (int i 1; i n; i) {if (val[i - 1] ! val[i]) {val[N] val[i];}}int tot n * (33 - Integer.numberOfLeadingZeros(N - 1)) 1;root new int[n];lc new int[tot];rc new int[tot];cnt new int[tot];sum new long[tot];// 依次插入每个元素构建持久化线段树for (int i 0; i n; i) {int idx Arrays.binarySearch(val, 0, N, a[i]);root[i] insert(idx, 0, N - 1, i 0 ? 0 : root[i - 1]);}}private int insert(int o, int l, int r, int pre) {int u no;cnt[u] cnt[pre] 1;sum[u] sum[pre] val[o];if (l r) return u;int m (l r) 1;if (o m) {lc[u] insert(o, l, m, lc[pre]);rc[u] rc[pre];} else {lc[u] lc[pre];rc[u] insert(o, m 1, r, rc[pre]);}return u;}// 查询区间 [l, r] 的第 k 小值public int smallK(int l, int r, int k) {int leftRoot l 0 ? 0 : root[l - 1];return smallK(k, 0, N - 1, leftRoot, root[r]);}private int smallK(int k, int l, int r, int i, int j) {if (l r) return val[l];int m (l r) 1;int leftCount cnt[lc[j]] - cnt[lc[i]];if (leftCount k) {return smallK(k - leftCount, m 1, r, rc[i], rc[j]);} else {return smallK(k, l, m, lc[i], lc[j]);}}// 查询区间 [l, r] 前 k 小的和public long smallKSum(int l, int r, int k) {int leftRoot l 0 ? 0 : root[l - 1];return smallKSum(k, 0, N - 1, leftRoot, root[r]);}private long smallKSum(int k, int l, int r, int i, int j) {if (l r) return (long) val[l] * k;int m (l r) 1;int leftCount cnt[lc[j]] - cnt[lc[i]];if (leftCount k) {return (sum[lc[j]] - sum[lc[i]]) smallKSum(k - leftCount, m 1, r, rc[i], rc[j]);} else {return smallKSum(k, l, m, lc[i], lc[j]);}}}---复杂度分析· 时间复杂度预处理 O(n log n)每个查询 O(log n)总体 O((n q) log n)· 空间复杂度O(n log n)
