33OJ
登录 注册

#ABC484E. 子段和统计

子段和统计

子段和统计

题目描述

给定一个长度为 NN 的序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

请你求出有多少个(非空的)连续子段,其元素之和在 LL 到 RR 之间(包含 LL 与 RR)。

这里,即使两个连续子段作为序列相等,只要它们取自不同的位置,就分别计数。

输入格式

输入第一行为三个整数 N,L,RN,L,R。

第二行为 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出一行一个整数,表示满足条件的连续子段个数。

5 -2 3
3 -1 -4 -1 5
8

样例 1 解释

满足条件的 (l,r)(l,r) 共有 88 组:

(1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)(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 解释

LL 与 RR 可以相等。

10 -126566 92319
11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587
34

数据范围

对于所有测试数据,保证:

  • 1≤N≤3×1051 \le N \le 3 \times 10^5;
  • −1018≤L≤R≤1018-10^{18} \le L \le R \le 10^{18};
  • −1012≤Ai≤1012-10^{12} \le A_i \le 10^{12};
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N≤2000N \le 2000
7∼127 \sim 12 N≤5×104N \le 5 \times 10^4
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。