题目概述给定一个长度为 n 的整数数组点数绝对值 ≤ 1000以及一个参数 k。定义“基番”为所有长度为 k 的连续子数组的元素和共有 t n - k 1 个基番。总番数定义为这些基番两两之间绝对差值的总和每个无序对只计算一次。要求计算总番数其中 n ≤ 5×10⁵。思路分析1. 朴素暴力不可行若直接求出所有基番然后用双重循环计算每对的绝对差时间复杂度为 O(t²)t 最大为 5×10⁵显然会超时。2. 关键优化点快速求基番使用前缀和O(n) 即可生成所有窗口和。高效计算两两绝对差之和将基番数组排序后利用前缀和将 O(t²) 降为 O(t)。核心推导排序后求绝对差之和设基番数组为a[0..t-1]。我们将其升序排序得到b[0] ≤ b[1] ≤ ... ≤ b[t-1]。对于任意一对(i, j)且i j因为b[j] ≥ b[i]所以|b[j]-b[i]| b[j] - b[i]。现在换个角度固定b[i]它作为较大值右侧元素时与它左侧所有元素i 个构成 i 个无序对每个对的差值为b[i] - b[p]p i总和为textb[i] * i - (b[0] b[1] ... b[i-1])其中括号内正是前缀和pref[i-1]。把所有 i 的贡献加起来就能得到所有无序对的绝对差之和且每对只被计算一次因为每个对只在较大值位置被计入。因此textans Σ_{i1}^{t-1} ( b[i]*i - pref[i-1] )i0 时贡献为 0可从 1 开始一代代码cpp#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); ll n, m; cin n m; vectorll pref(n 1, 0); for (ll i 1; i n; i) { cin pref[i]; pref[i] pref[i - 1]; } ll K n - m 1; vectorll win(K); for (ll i 0; i K; i) { win[i] pref[i m] - pref[i]; } sort(win.begin(), win.end()); ll sum 0; vectorll ans(K, 0); for (ll i 0; i K; i) { ans[i] (i 0 ? win[i] : ans[i - 1] win[i]); } for (ll i K - 1; i 0; i--) { sum win[i] * i - ans[i - 1]; } cout sum \n; return 0; }代码亮点使用前缀和pref快速生成窗口和空间 O(n)。对win排序后利用前缀和ans这里ans存储的是win的前缀和命名容易混淆通过单循环计算总和时间复杂度 O(t log t)满足题目要求。循环从K-1到1恰好对应公式中的 i 从 1 到 K-1逻辑正确。潜在问题数据溢出总番数可能超过 64 位有符号整数long long能表示的范围。虽然点数绝对值 ≤ 1000但 n 可达 5×10⁵窗口和最大约 5×10⁸无序对个数约 1.25×10¹¹乘积可达到 6.25×10¹⁹超过 9.22×10¹⁸LLONG_MAX因此必须使用__int128累加并手动输出。改进后的完整代码范围更大以下代码保留核心逻辑仅将累加变量改为__int128并增加了输出处理。cpp#include bits/stdc.h using namespace std; typedef long long ll; // 输出 __int128 的辅助函数 void print_int128(__int128 x) { if (x 0) { cout 0; return; } if (x 0) { cout -; x -x; } string s; while (x 0) { int digit x % 10; s.push_back(0 digit); x / 10; } reverse(s.begin(), s.end()); cout s; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); ll n, m; cin n m; vectorll pref(n 1, 0); for (ll i 1; i n; i) { cin pref[i]; pref[i] pref[i - 1]; } ll K n - m 1; vectorll win(K); for (ll i 0; i K; i) { win[i] pref[i m] - pref[i]; } sort(win.begin(), win.end()); // 存储 win 的前缀和 vectorll prefWin(K, 0); for (ll i 0; i K; i) { prefWin[i] win[i] (i 0 ? 0 : prefWin[i - 1]); } __int128 total 0; for (ll i K - 1; i 0; --i) { total (__int128)win[i] * i - (__int128)prefWin[i - 1]; } print_int128(total); cout \n; return 0; }改动说明将sum的类型改为__int128并在乘法时强制转换避免溢出。添加print_int128函数因为标准库不支持直接输出__int128。更清晰地命名前缀和数组为prefWin避免与答案变量混淆。复杂度分析时间复杂度前缀和 O(n)生成窗口 O(t)排序 O(t log t)最后求和 O(t)总复杂度 O(n log n)对于 n5×10⁵ 完全可行。空间复杂度存储前缀和prefn1、窗口数组wint及其前缀和prefWint均为 O(n)。易错点提醒索引越界生成窗口时i m不会超过 n因为 i ≤ n - m。循环边界在最后的求和循环中i从 K-1 到 1注意 K 最小为 1此时循环不执行结果 0。数据溢出即便使用__int128也要确保中间乘法win[i] * i不会在计算时溢出因此强制转换为__int128再乘。负数的处理窗口和可能为负数数组含有负数但排序后仍然可以计算公式适用。__int128支持负数输出函数已处理负号。总结通过前缀和 排序 前缀和技巧我们将问题复杂度从 O(n²) 降到 O(n log n)并处理了超大整数输出。本题核心在于将“求两两绝对差之和”转化为排序后的单侧贡献是经典算法题型的变体值得熟练掌握。