子段和统计
题目描述
给定一个长度为 N 的序列 A=(A1,A2,…,AN)。
请你求出有多少个(非空的)连续子段,其元素之和在 L 到 R 之间(包含 L 与 R)。
这里,即使两个连续子段作为序列相等,只要它们取自不同的位置,就分别计数。
输入格式
输入第一行为三个整数 N,L,R。
第二行为 N 个整数 A1,A2,…,AN。
输出格式
输出一行一个整数,表示满足条件的连续子段个数。
5 -2 3
3 -1 -4 -1 5
8
样例 1 解释
满足条件的 (l,r) 共有 8 组:
(1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)。
6 0 0
0 0 0 0 0 0
21
样例 2 解释
L 与 R 可以相等。
10 -126566 92319
11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587
34
数据范围
对于所有测试数据,保证:
- 1≤N≤3×105;
- −1018≤L≤R≤1018;
- −1012≤Ai≤1012;
- 所有输入值均为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 |
分值 |
每个测试点 |
特殊性质 |
| 1∼6 |
30 |
5 |
N≤2000 |
| 7∼12 |
N≤5×104 |
| 13∼20 |
40 |
无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。