求解满足i<j且A[i]<=A[j]+c的数对个数（不接受O(N²)解法）

该问题完全可以基于归并排序求逆序对的扩展思路求解，可稳定达到*O(N log N)*的时间复杂度，满足非O(N²)的要求。

思路适配性说明 #

你之前了解的逆序对思路求解A[i] > 2*A[j]类数对的逻辑完全适配本题。题目的约束条件i<j 且 A[i] <= A[j] + c可以直接移项等价为A[i] - A[j] <= c，和特殊逆序对的统计逻辑本质一致：都是在不破坏原始索引先后约束的前提下，利用有序性批量统计符合条件的数对，避免暴力枚举。
你之前担心的“原数组无序、排序打乱i<j顺序”的问题，在归并分治框架下不会出现——归并的拆分是严格按照原始索引位置切分的，左子区间的所有元素原始索引永远小于右子区间的元素，天然满足i<j的前提，不会出现索引顺序错乱导致的误统计。

归并分治具体实现步骤 #

• 分治拆分：和标准归并排序逻辑一致，将当前处理的数组区间从中间位置切分为左右两个子区间，先递归统计左子区间内部、右子区间内部符合要求的数对数量。
• 跨区间数对统计：递归处理完子区间后，左右子数组已经各自保持升序。此时用双指针线性统计跨左右的符合条件的数对：初始化左指针p指向左数组起始位置，依次遍历右数组的每个元素A[j]，单向移动p直到找到左数组中第一个满足A[i] > A[j] + c的位置，此时左数组中p位置前的所有元素和当前A[j]都满足题设不等式要求，直接将p对应的偏移量累加到总计数中。这一过程两个指针都只会单向移动，时间复杂度为O(N)。
• 归并合并：和标准归并排序操作一致，将当前左右两个有序子数组合并为一个升序数组，返回给上层递归调用即可。

其他可选O(N log N)方案 #

除了归并分治思路，你也可以选择离散化+树状数组的离线解法：

1. 提前收集数组中所有A[i]、A[i] + c的取值，做坐标离散化压缩，解决数值范围过大的问题
2. 从数组末尾向前遍历，每遍历到元素A[j]，先查询树状数组中落在(-∞, A[j] + c]区间内的元素总数，累加到总计数
3. 将当前A[j]的取值更新到树状数组的对应位置，继续向前遍历即可

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