A12165. Petya and Array
编程题
普及/提高-
知识点
题目描述
Petya has an array $a$ consisting of $n$ integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.
Now he wonders what is the number of segments in his array with the sum less than $t$ . Help Petya to calculate this number.
More formally, you are required to calculate the number of pairs $l, r$ ( $l \le r$ ) such that $a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$ .
Petya 有一个由 $n$ 个整数组成的数组 $a$ 。他最近学会了部分求和，现在他可以非常快速地计算数组任意段上的元素之和。段是数组中一个挨着一个的非空元素序列。
现在他想知道数组中总和小于 $t$ 的数段有多少。请帮助 Petya 计算这个数字。
更正式地说，您需要计算出 $l, r$ ( $l \le r$ ) 中有多少对是 $a_l + a_{l+1} + \dots + a_{r-1} + a_r \lt t$ 。
Now he wonders what is the number of segments in his array with the sum less than $t$ . Help Petya to calculate this number.
More formally, you are required to calculate the number of pairs $l, r$ ( $l \le r$ ) such that $a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$ .
Petya 有一个由 $n$ 个整数组成的数组 $a$ 。他最近学会了部分求和，现在他可以非常快速地计算数组任意段上的元素之和。段是数组中一个挨着一个的非空元素序列。
现在他想知道数组中总和小于 $t$ 的数段有多少。请帮助 Petya 计算这个数字。
更正式地说，您需要计算出 $l, r$ ( $l \le r$ ) 中有多少对是 $a_l + a_{l+1} + \dots + a_{r-1} + a_r \lt t$ 。
输入格式
The first line contains two integers $n$ and $t$ ( $1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$ ).
The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ ( $|a_{i}| \le 10^{9}$ ) — the description of Petya's array. Note that there might be negative, zero and positive elements.
输入
第一行包含两个整数 $n$ 和 $t$ ( $1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$ )。
第二行包含一串整数 $a_1, a_2, \dots, a_n$ ( $|a_{i}| \le 10^{9}$ ) - Petya 的数组描述。请注意，可能存在负、零和正元素。
The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ ( $|a_{i}| \le 10^{9}$ ) — the description of Petya's array. Note that there might be negative, zero and positive elements.
输入
第一行包含两个整数 $n$ 和 $t$ ( $1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$ )。
第二行包含一串整数 $a_1, a_2, \dots, a_n$ ( $|a_{i}| \le 10^{9}$ ) - Petya 的数组描述。请注意，可能存在负、零和正元素。
输出格式
Print the number of segments in Petya's array with the sum of elements less than $t$ .
输出
打印 Petya 数组中元素总和小于 $t$ 的段的数量。
输出
打印 Petya 数组中元素总和小于 $t$ 的段的数量。
输入输出样例
输入 #1
5 4 5 -1 3 4 -1
输出 #1
5
输入 #2
3 0 -1 2 -3
输出 #2
4
输入 #3
4 -1 -2 1 -2 3
输出 #3
3
说明/提示
In the first example the following segments have sum less than $4$ :
- $[2, 2]$ , sum of elements is $-1$
- $[2, 3]$ , sum of elements is $2$
- $[3, 3]$ , sum of elements is $3$
- $[4, 5]$ , sum of elements is $3$
- $[5, 5]$ , sum of elements is $-1$
备注
在第一个示例中，以下线段的总和小于 $4$ ：
- $[2, 2]$ ，元素总和为 $-1$ 。
- $[2, 3]$ ，元素总和为 $2$ 。
- $[3, 3]$ ，元素之和为 $3$ 。
- $[4, 5]$ ，元素之和为 $3$ $[5, 5]$ , 元素之和为 $3$ $[5, 5]$ .
- $[5, 5]$ ，元素之和为 $-1$
- $[2, 2]$ , sum of elements is $-1$
- $[2, 3]$ , sum of elements is $2$
- $[3, 3]$ , sum of elements is $3$
- $[4, 5]$ , sum of elements is $3$
- $[5, 5]$ , sum of elements is $-1$
备注
在第一个示例中，以下线段的总和小于 $4$ ：
- $[2, 2]$ ，元素总和为 $-1$ 。
- $[2, 3]$ ，元素总和为 $2$ 。
- $[3, 3]$ ，元素之和为 $3$ 。
- $[4, 5]$ ，元素之和为 $3$ $[5, 5]$ , 元素之和为 $3$ $[5, 5]$ .
- $[5, 5]$ ，元素之和为 $-1$