连续子区间和

题解：

考察点： 滑动窗口，数形结合

易错点：

在本题中数据范围为，如果使用暴力求解是行不通的，因为如果使用复杂度为的暴力，那运算次数将达到，一般来说，在时间范围内所能抗住的运算次数在

解法：滑动窗口

首先，先从下图来观察出一个很重要的结论：

对于一个全由正整数构成的序列来说，如果区间中所有元素的和大于等于，则区间中所有元素的和一定大于等于。这是一个非常显然的结论，但在这里却非常有用。假设位置为区间和的分隔线，中所有元素的和大于等于，则当前位置对答案的贡献为，因为后面无论加上多少个元素，总可以，满足区间的和大于等于。

有了上述结论，可以很自然使用滑动窗口算法来做这个问题。对于当前位置，指针指向其所对应区间的开头。如果大于，则指针从的开始位置往后移动，直到所对应的区间小于为止。同时指针每移动一次，对答案的贡献增加，因为其后的都满足大于等于。整个过程中最多遍历1次，遍历一次，所以复杂度为，也就是级别的复杂度

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e6+100;
typedef long long LL;
int n,a[maxn];
LL x;
int main()
{
    scanf("%d%lld",&n,&x);
    LL sum=0,ans=0;
    int j=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
        if(sum>=x){
            ans+=n-i+1;
            while(j<=i&&sum>=x){
                sum-=a[j];
                j++;
                if(sum>=x) ans+=n-i+1;
                else break;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}