小红统计区间（hard） - 树状数组 + 离散化

本文主要是介绍小红统计区间（hard） - 树状数组 + 离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

存在负数不满足单调性，因此无法二分或者双指针，对于每一段符合条件的区间 $[l, r]$ 都有 $s u m [r] - s u m [l - 1] >= k$ ，也就是 $s u m [l - 1] <= s u m [r] - k$ ，那么如果对于所有区间的前缀和来进行顺序存储，那么对于当前前缀和 $s u m [i]$ ，可以去找小于等于 $s u m [i] - k$ 的符合条件的前缀和有多少，但是前缀和的范围很大，所以就要进行离散化，将所有需要用到的前缀和都进行i离散化重新定下标，然后可以通过树状数组每次对遍历到的前缀和的位置加一，统计可以加上树状数组查询 $s u m [i] - k$ 的结果，也就是这之前有多少个满足条件的前缀和。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;const int N = 2e5 + 10;ll a[N];
int tr[N];
map<ll, int> m;void add(int u) {for(int i = u; i < N; i += (i & -i)) {tr[i] ++;}return ;
}int query(int x) {int ans = 0;for(int i = x; i >= 1; i -= i & -i) ans += tr[i];return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;ll k;cin >> n >> k;for(int i = 1; i <= n; i ++) {cin >> a[i];a[i] += a[i - 1];}m[0] = 1;for(int i = 1; i <= n; i ++) {m[a[i]] = 1;m[a[i] - k] = 1;}int now = 1;for(auto &x: m) {x.second = now ++;}//for(auto j: m) cout <<j.first << ' ' <<  j.second << endl;ll ans = 0;add(m[0]);for(int i = 1; i <= n; i ++) {ans += query(m[a[i] - k]);add(m[a[i]]);}cout << ans << "\n";
}