小红统计区间（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≤1051 ≤ a i ≤ 10 9 1≤a_i≤10^91≤ai​≤1091 ≤ k ≤ 10 14 1≤k≤10^{14}1≤k≤1014输出描述输出一个整数表示满足条件的非空区间个数。示例1输入5 5 1 4 2 1 3输出8解题思路本题依托滑动窗口双指针高效统计满足条件的区间数利用数组元素均为正整数的特性前缀和严格递增先初始化左指针l 1 l1l1、区间和s u m 0 sum0sum0、答案a n s 0 ans0ans0遍历右指针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−r1n−r1个均满足和≥ k ≥k≥k将该数量累加到a n s ansans随后不断右移左指针l ll并减去a [ l ] a[l]a[l]直到s u m k sumksumk最终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)精准且高效地统计出符合要求的区间数量。总结核心逻辑利用正整数数组前缀和递增的特性滑动窗口快速定位以r rr为右端点的最小合法左端点。关键计算找到最小左端点后直接累加n − r 1 n−r1n−r1以r为右端点的合法区间数。时间复杂度O ( n ) O(n)O(n)适配大数据量场景避免暴力枚举的低效问题。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll N1e510;constll p1e97;intmain(){intn;ll k;cinnk;vectorlla(n1);for(ll i1;in;i)cina[i];ll ans0,sum0;ll l1;for(ll r1;rn;r){suma[r];while(lrsumk){ansn-r1;sum-a[l];l;}}coutansendl;return0;}