L题-前缀和加树状数组
简单的异或
https://ac.nowcoder.com/acm/contest/63602/A
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;
}
