[归并排序]leetcode327：区间和的个数(hard)

题目：

题解：

思路：归并排序

1）对于区间和的快速求解需要使用前缀和，由于 a 中的元素有正有负，所以前缀和数组不是单调递增的，我们可以对前缀和数组进行归并排序，顺便计算区间和的个数，求 pre[j]-pre[i]∈[lower,upper] 的 (i,j) 的个数。2）思考如何利用两个升序数组n1,n2求出n2[j]-n1[i]∈[lower,upper]？
3）在解决这一问题后，原问题就迎刃而解了：我们采用归并排序的方式，能够得到左右两个数组排序后的形式，以及对应的下标对数量。对于原数组而言，若要找出全部的下标对数量，只需要再额外找出左端点在左侧数组，同时右端点在右侧数组的下标对数量，而这正是我们此前讨论的问题。

代码如下：

const int N = 1e5+10;
using LL = long long;
class Solution {
public:
    // 思路：归并排序，在两个升序数组中寻找下标对的区间和在[lower,upper]之间。每次统计第二个区间的n2[l]>=n1[0]+lower,n2[r]>n1[0]+uperr，这样的话[l,r)范围内的区间和都在[lower,upper]之间了。由于n1是递增的，因此l，r只能向右移动才能进行统计了。
    LL pre[N],b[N];
    int countRangeSum(vector& a, int lower, int upper) {
        int n=a.size();
        memset(pre,0,sizeof pre),memset(b,0,sizeof b);
        // 预处理前缀和数组
        for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i-1];
        return merge(lower,upper,0,n);
    }

    int merge(int lower,int upper,int l,int r){
        if(l>=r)return 0;
        // 1.确定分界点，递归处理左右两段
        int mid=(l+r)>>1;
        int res=merge(lower,upper,l,mid)+merge(lower,upper,mid+1,r);
        // 2.统计下标对的数量
        int i=l,_l=mid+1,_r=mid+1;
        while(i<=mid)
        {
            // 直到pre[_l]-pre[i]>=lower为止；直到pre[_r]-pre[i]>upper为止；这样区间[_l,_r)满足情况了
            while(_l<=r&&pre[_l]-pre[i]mid)b[k++]=pre[j++];
            else if(j>r)b[k++]=pre[i++];
            else{
                if(pre[i]