概要
本题要在一个数组中寻找子数组，使得其和落在指定区间内，输出满足条件的数组的个数。要求复杂度低于$O(n^2)$。
方法一 暴力求解
您很容易想到$O(n^2)$的暴力求解方法，仅须两层循环将所有子序列的和求出来即可，代码简单，运行的结果也很明了——TLE。
方法二 修改版归并排序
事实上，本题是一个归并排序的题目。
Step 1 求前n项和数组
由于寻找子数组是一个十分麻烦的事情，首先要将原问题进行转化。很容易想到，对于序列$a_i$，任意一个子序列的和
$$
S(a)_{ij} = S(a)_i - S(a)_j
$$
因此对于输入长度为$n$的数组$A$，可以求得一个长度为$n+1$的前n项和数组$S$，那么问题就转化为在该数组中寻找一个元组$(i, j)$，使得
$$
lower \le S_j - S_i \le upper, i \le j
$$
因此算法的第一步是求前n项和数组$S$，遍历一遍数组即可，复杂度为$O(n)$。
Step 2 分治
最容易想到的分治就是对半分，本题用对半分对原问题进行分解也是足够的。求给定前n项和数组满足条件的元组个数，先求其前半部分的元组个数，再求其后半部分的元组个数，最后进行组合。根据大师定理，有复杂度的递归表达式
$$
T(n) = 2T(\frac{n}{2}) + O(?)
$$
要使得复杂度低于$O(n^2)$，表达式最后的项也必须低于$O(n^2)$，也就是组合的过程复杂度不能出现两层循环。
直观来看，对于两个长度为$\frac{n}{2}$的子数组，已知各自满足条件的元组个数，那么剩下的事情就是各自寻找一个元素组成元组，看是否满足题目要求——后面的与前面的差落在给定范围内，显然，对于两个无序的数组是很难做到复杂度低于$O(n^2)$的，那么考虑将数组排序。
对于两个有序的数列，可以在$O(n)$的复杂度内找到满足条件的元组个数，令两个数组为$L$，$R$，首先有，如果
$$
R_m - L_i \ge lower \
R_n - L_i \le upper \
m \le n
$$
那么与$L_i$能组成的元组个数即为$n - m$，其次有一个简单但是十分的重要发现，若有
$$
R_m - L_i < lower \
R_n - L_i \le upper
$$
则，
$$
R_m - L_k < lower \ \forall k \in [0, i] \
R_n - L_k \le upper \ \forall k \in [0, i]
$$
也就是说，对于每一个在$L$中的元素，并不需要便利所有$R$中的元素以找到$m, n$的值，由于$m, n$的值只会增加，不会减少，因此对于所有$L$中的元素仅须便利一次$R$即可，复杂度降为$O(n)$。
那么最后的问题就是如何得到两个有序的子数列，直接排序会使得复杂度提升为$O(nlogn)$，显然是行不通的。很容易看到这个分治的过程与归并排序的过程一致，因此在过程中“顺便”给每个子数组进行归并排序即可，即把当前的计数求出来后，将两个数组按归并排序算法合成即可，复杂度为$O(n)$。
最终，根据大师定理，对于递归表达式
$$
T(n) = 2T(\frac{n}{2}) + O(n)
$$
整个算法的复杂度为$T(n) = O(nlogn)$，题目也接受了这个复杂度，Accepted。
附录
本人解答用了一个std::inplace_merge简化了归并操作，注意要先向下分解，从最底层开始求次数、归并。