离散化 + 树状数组

求解所有元素之和不小于k的非空区间数量：

  1. 求解前缀和
  2. 对前缀和进行排序然后离散化
  3. 树状数组维护小于s[i] - k的值的数量

因为树状数组需要查询小于s[i] - k的数量，所以离散化时需要把每个s[i] - k一起排序离散化

add(get(0), 1) 把0首先加入树状数组，因为从开头到某一个元素也可能是一个满足条件的区间

因为s[i] - k也加入离散化，树状数组开到2 * n

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#define ios { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fios ofstream out("test.txt");cout.rdbuf(out.rdbuf())
#define endl "\n"
#define lowbit(x) (x & (-x))
#define INF 0x3f3f3f3f
#define MINF 2147483647
#define eps 1e-6
#define PI acos(-1)
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 200010;

int n;
LL k;
int a[N];
LL s[N], tr[N];
vector<LL> alls;

void add(int x, int c)
{
    for(int i = x; i <= N; i += lowbit(i))
        tr[i] += c;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int get(LL x)
{
    int l = 0, r = alls.size();
    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l + 1;
}

int main()
{
    ios;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    for(int i = 1; i <= n; i++) alls.push_back(s[i]), alls.push_back(s[i] - k);

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    LL res = 0;
    add(get(0), 1);
    for(int i = 1; i <= n; i++)
    {
        res += query(get(s[i] - k));
        add(get(s[i]), 1);
    }

    cout << res << endl;

    return 0;
}