/*
 * @lc app=leetcode.cn id=327 lang=cpp
 *
 * [327] 区间和的个数
 */

// @lc code=start
class Solution {
private:
    vector<long> temp;
    vector<long> preSum;
    int count = 0;
    int lower, upper;

    void sort(vector<long>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    } 

    void merge(vector<long>& nums, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }

        int start = mid + 1, end = mid + 1;
        for (int i = lo; i < mid + 1; i++) {
            while (start <= hi && nums[start] - nums[i] < lower) {
                start++;
            }
            while (end <= hi && nums[end] - nums[i] <= upper) {
                end++;
            }
            count += end - start;
        }

        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }

public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        this->lower = lower;
        this->upper = upper;
        preSum.resize(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            preSum[i+1] = (long)nums[i] + preSum[i];
        }
        temp.resize(preSum.size(), 0);
        sort(preSum, 0, preSum.size() - 1);
        return count;
    }
};
// @lc code=end