L题-前缀和加树状数组

先求前缀和T，方便进行区间操作，这样我们枚举每一个右端点R，查找有多少个左端点L满足 T[R] - T[L] >= x 转化为多少个T[L] 满足 T[L] <= T[R] - x。

这种值域问题采用树状数组维护桶，每次枚举完一个右端点将其T[R]的位置加+，由于值域过大需要离散化。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 5;
int a[N], bit[N * 2], T[N];
vector<int> ve(1, -1e18);
int n, m, ans;

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

void update(int p) {
    for (int i = p; i < N * 2; bit[i]++, i += lowbit(i));
}

int query(int p) {
    int res = 0;
    for (int i = p; i; res += bit[i], i -= lowbit(i));
    return res;
}

signed main(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        T[i] = T[i - 1] + a[i];
        ve.push_back(T[i]);
        ve.push_back(T[i] - m);
    }
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    for (int i = 1; i <= n; i++) {
    	if (T[i] >= m)
    		ans++;
        ans += query(lower_bound(ve.begin(), ve.end(), T[i] - m) - ve.begin());
        update(lower_bound(ve.begin(), ve.end(), T[i]) - ve.begin());
    }
    cout << ans << endl;
    return 0;
}