解题思路

本题由于原数组a中存在负数，扩大区间范围可能会导致区间和反倒减少，因此不能简单使用滑动窗口。

假设已知前缀和数组sum，那么区间和 s[l, r] = sum[r] - sum[l - 1] >= k的必要条件为

sum[l - 1] <= sum[r] - k。

我们对于每一个右边界r，判断其左边存在多少个左边界l，满足不等式sum[l - 1] <= sum[r] - k，就代表存在多少个满足条件的解。为了快速判断小于等于 sum[r] - k的数量，这里用到树状数组。

此外，本题的数据量为10^5，而数据范围在10^14，因此开树状数组的时候必须用到离散化。

知识点：树状数组

链接 - 树状数组详解

如果对于树状数组不了解的，先看上面链接。

对于本题，我们要统计数组中值小于等于x的元素个数的时候，可以将其分解为若干个区间。以数字7为例，统计数组中小于等于7的元素的个数。那么ans = c[7] + c[6] + c[4]。其中c[4]值为区间[1, 4]的个数，c[6]值为区间[5, 6]的个数，c[7]为区间[7, 7]的个数。

一般的，c[x]值为区间[x - lowbit(k) + 1, x]的个数。我们在写函数query时只要做一个递归即可。

接下来是update函数，也就是向数组中添加元素x，那么所有包含了元素x的区间对应的c[y]值+1。比如我们要向数组添加元素5。那么c[5]++，c[8]++，c[16]++，c[32]++，以此类推，直到超出数组c的界限为止。

知识点：离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

原数据：{100,200}，{20,50000}，{1,400}；处理后：{3,4}，{2,6}，{1,5}；

对应到本题，如果不进行离散化映射，那么树状数组就必须开非常大，最高达到10^14。

一般的离散化步骤包括：排序、去重、索引。用到的函数有用于去重的unique()函数，以及二分查找函数lower_bound()、upper_bonud()，用于计算对应元素在数组中的位置。

我的代码使用了容器set和unordered_map来达成相同的作用。

注意，由于要查询sum[r] - k的值，因此进行离散化映射的时候，也要把所有的sum[r] - k映射到map中。

下面是cpp代码。

#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;

vector<long long> c; //树状数组，元素为对应区间数的个数

int lowbit(int x) {
    return x & -x;
}

void update(int x) { //向数组中添加元素x
    while (x < c.size()) {
        ++c[x];
        x += lowbit(x);
    }
}

int query(int x) { //查询小于等于x的数量
    long long ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    int n, a;
    long long k, ans = 0;
    cin >> n >> k;
    vector<long long> sum(n + 1); //前缀和
    set<long long> s; //前缀和与所有sum[i]-k的集合
    sum[0] = 0;
    s.insert(0);
    for (int i = 1; i <= n; ++i) {
        cin >> a;
        sum[i] = sum[i - 1] + a;
        s.insert(sum[i]);
        s.insert(sum[i] - k);
    }
    unordered_map<long long, int> mp; //离散化映射
    int cnt = 0; 
    for(auto &i : s) {
        mp[i] = ++cnt;
    }
    c.resize(cnt + 1); //设置树状数组容量
    update(mp[0]); //将最初的sum[0] = 0加入树状数组
    for(int i = 1; i <= n; ++i) {
        ans += query(mp[sum[i] - k]); //查询
        update(mp[sum[i]]); //sum[i]加入树状数组，用于后续查询
    }
    cout << ans;
}