AT_abc484_e.Subsegment Sum Finder
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a sequence A=(A1,A2,…,AN) of length N. Find the number of (non-empty) contiguous subsequences whose sum is between L and R, inclusive.
Here, even if two contiguous subsequences are equal as sequences, they are counted separately if they are taken from different positions.
给你一个长度为 N 的序列 A=(A1,A2,…,AN)。求和在 L 到 R 之间(含端点)的(非空)连续子序列的个数。
注意:即使两个连续子序列作为序列完全相同,只要它们起始或结束位置不同,就视为不同的子序列,分别计数。
输入格式
The input is given from Standard Input in the following format:
N L R
A1 A2 … AN
输入从标准输入中按以下格式给出:
N L R
A1 A2 … AN
输出格式
Print the answer.
输出答案。
输入输出样例
输入#1
5 -2 3 3 -1 -4 -1 5
输出#1
8
输入#2
6 0 0 0 0 0 0 0 0
输出#2
21
输入#3
10 -126566 92319 11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587
输出#3
34
说明/提示
Sample 1 Explanation:
For this input, there are 8 pairs (l,r) such that the contiguous subsequence from the l-th through r-th elements satisfies the condition:
- (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)
Sample 2 Explanation:
It is possible that L=R.
Constraints
- All input values are integers.
- 1≤N≤3×105
- −1018≤L≤R≤1018
- −1012≤Ai≤1012
样例 1 解释:
对于该输入,共有 8 对 (l,r),使得从第 l 个元素到第 r 个元素的连续子序列满足题目条件:
- (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)
样例 2 解释:
有可能出现 L=R 的情况。
约束条件
- 所有输入值均为整数。
- 1≤N≤3×105
- −1018≤L≤R≤1018
- −1012≤Ai≤1012
输入解题思路,AI测评打分。不知道怎么写?