小红统计区间（easy）【牛客tracker 每日一题】

小红统计区间（easy）

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

本题为easy版本，和hard版本的唯一区别是a i a_iai​保证是正整数！

小红拿到了一个数组，她想知道，有多少非空区间满足区间所有元素之和不小于k kk？

输入描述：

第一行输入两个正整数n , k n,kn,k，用空格隔开。
第二行输入n nn个正整数a i a_iai​，代表数组的元素。
1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤105
1 ≤ a i ≤ 10 9 1≤a_i≤10^91≤ai​≤109
1 ≤ k ≤ 10 14 1≤k≤10^{14}1≤k≤1014

输出描述：

输出一个整数表示满足条件的非空区间个数。

示例1

输入：

5 5 1 4 2 1 3

输出：

8

解题思路

本题依托滑动窗口（双指针）高效统计满足条件的区间数，利用数组元素均为正整数的特性（前缀和严格递增）：先初始化左指针l = 1 l=1l=1、区间和s u m = 0 sum=0sum=0、答案a n s = 0 ans=0ans=0；遍历右指针r rr从1 11到n nn，累加a [ r ] a[r]a[r]到s u m sumsum中，当s u m ≥ k sum≥ksum≥k时，说明以r rr为右端点、左端点≥ l ≥l≥l的所有区间（共n − r + 1 n−r+1n−r+1个）均满足和≥ k ≥k≥k，将该数量累加到a n s ansans，随后不断右移左指针l ll并减去a [ l ] a[l]a[l]，直到s u m < k sum<ksum<k；最终a n s ansans即为满足条件的非空区间总数。该方法时间复杂度为O ( n ) O(n)O(n)，每个元素仅被左右指针各访问一次，适配n ≤ 1 e 5 、 k ≤ 1 e 14 n≤1e5、k≤1e14n≤1e5、k≤1e14的规模，通过滑动窗口避免枚举所有区间（ O ( n 2 ) ） （O(n²)）（O(n2)），精准且高效地统计出符合要求的区间数量。

总结

1. 核心逻辑：利用正整数数组前缀和递增的特性，滑动窗口快速定位以r rr为右端点的最小合法左端点。
2. 关键计算：找到最小左端点后，直接累加n − r + 1 n−r+1n−r+1（以r为右端点的合法区间数）。
3. 时间复杂度：O ( n ) O(n)O(n)，适配大数据量场景，避免暴力枚举的低效问题。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll N=1e5+10;constll p=1e9+7;intmain(){intn;ll k;cin>>n>>k;vector<ll>a(n+1);for(ll i=1;i<=n;i++)cin>>a[i];ll ans=0,sum=0;ll l=1;for(ll r=1;r<=n;r++){sum+=a[r];while(l<=r&&sum>=k){ans+=n-r+1;sum-=a[l];l++;}}cout<<ans<<endl;return0;}