题解 | #小红统计区间（hard）只离散化S[i]

这题大部分题解都是 和 放进去，其实只离散化 也是可以的.

每次查询目标值在离散化数组的排名，然后查询排名数量即可。

这样做的时间复杂度是 ，常数应该是上面写法的2倍左右，不过实测速度挺快名列前茅

代码如下：

#include <iostream>
#include <algorithm>
#define lowbit(x) (x)&(-x)
using namespace std;
using ll = long long;
const int N = 1e5 + 7;

ll s[N], ss[N];
int fa[N];
int n, len;
ll k, ans;

void add(int x, int y) {
    for (; x <= len; x += lowbit(x)) fa[x] += y;
}

int ask(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res += fa[x];
    return res;
}

int get_rank(ll& x) { //获取在原数组的排名
    return lower_bound(ss, ss + len, x) - ss + 1;
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
        ss[i] = s[i];
    }
    ss[0] = s[0];

    sort(ss, ss + n + 1);
    len = unique(ss, ss + n + 1) - ss;

    add(get_rank(s[0]), 1);
    ans = 0;

    for (int i = 1; i <= n; i++) {
        ll t = s[i] - k;
        int pos = lower_bound(ss, ss + len, t) - ss;
        if (pos < len && ss[pos] > t) {
            pos--;
        }
        ans += ask(pos + 1);
        add(get_rank(s[i]), 1);
    }

    cout << ans ;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int tt = 1;
    while (tt--) solve();
    return 0;
}