DSA题解：统计满足a[i]-a[j]+c≤b[i]-b[j]+d且i<j的数对个数

给定长度均为n的数组a、b，常数c、d，统计所有满足i < j且不等式a[i] - a[j] + c <= b[i] - b[j] + d的数对(i,j)总数量，要求时间复杂度低于O(n²)。

第一步永远是先对不等式做代数变形，把同下标的项归类到同侧，不要一开始就想着套数据结构：

对原式移项整理：
把所有带下标i的项移到不等号左侧，所有带下标j的项移到右侧：
a[i] - b[i] <= a[j] - b[j] + (d - c)

这时候问题会直接简化：我们定义新数组x，其中x[k] = a[k] - b[k]，再定义常数k_val = d - c，原问题就变成了统计单数组x中，满足i<j且x[i] <= x[j] + k_val的数对总数——这是非常经典的区间计数类问题，和逆序对统计属于同一类题型，完全可以在O(nlogn)时间复杂度下解决。

你一开始考虑的哈希数组思路之所以走不通，核心问题是如果a、b的元素取值范围很大（比如达到1e9量级），直接开数组存计数会完全超出内存限制；如果用普通哈希表存频次，查询前缀和的时候又没法做到高效，最终还是会退化成O(n²)的复杂度。

方案1：归并排序统计（类逆序对写法） #

这个方案不需要处理数值离散化，逻辑和统计逆序对几乎完全一致：

• 首先预处理算出x数组和常数k_val
• 套用归并排序的分治框架：每次把数组拆成左右两个有序子数组时，左半部分所有元素的下标都严格小于右半部分元素的下标，这时候用双指针可以O(n)时间统计跨左右两部分的符合条件的数对数量
• 统计完当前层的数对后，正常执行归并排序的合并操作，保证返回给上层的子数组是有序的
• 整个过程没有额外的数值范围要求，时间复杂度稳定O(nlogn)，空间复杂度O(n)

方案2：离散化+树状数组（离线处理） #

这个方案代码实现更短，适合熟悉树状数组的场景：

• 同样先预处理算出x数组和常数k_val
• 因为我们只需要关心数值的相对大小关系，所以提前把所有会用到的数值（所有x[i]、所有x[i]+k_val，共2n个值）收集起来，排序去重后映射到连续的整数下标，这个过程就是离散化，处理完后树状数组的大小最多只有2n，完全不会有内存问题
• 从左到右遍历数组，处理到下标j的时候，所有i<j的x[i]已经被加入树状数组了，此时只需要查询树状数组中，值小于等于x[j] + k_val的元素总个数，累加到答案里；之后再把当前的x[j]更新到树状数组中即可
• 整个过程的时间复杂度也是O(nlogn)，空间复杂度O(n)

内容的提问来源于stack exchange，提问作者Kwaku Kusi