题目描述
给定一个数组a，一位不愿透露姓名的帅气（至少名字帅）的同学想要询问满足i≤j 且L≤a[i]+a[i+1]+...+a[j]≤R 的点对 (i,j) 的数量。
考点为第一次上机C、H题知识点的综合（前缀和+归并排序）。
输入
第一个数为数据组数T，每组数据两行。
第一行为整数n, L, R，表示序列长度，L，R；
接下来一行为空格分隔的n个整数。
1≤T≤5.
1≤n≤1e6.
0≤a[i]≤1000.
0≤L,R≤1e9.
输出
对于每组数据，输出一行，点对的数量
输入样例
1
3 1 2
2 1 1
输出样例
4
HINT
样例4组分别为(1, 1), (2, 2), (3, 3), (2, 3)
思路
一个区间[l, r]的和，可以表示成sum[r] – sum[l – 1]，sum为前缀和数组。所以即为上次上机CH题。做一遍前缀和，数组第一项添加一个0，复制一遍上次上机H题代码即可。
参考代码