在有负数的情况下,如何快速统计先前的合法区间?
把全部前缀丢到权值线段树上即可 ,记得先离线后离散
int n, m, k;
int a[N];
int pre[N];
int ans;
void Sakuya()
{
cin >> n >> k;
vector<int>b;
b.emplace_back(0);
for(int i = 1; i <= n; ++ i){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
b.emplace_back(pre[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto get = [&](int x) -> int{
return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
};
int siz = b.size() + 5;
vector<int>tr(siz * 4 + 5);
auto pushup = [&](int x, int y) -> int{
return x + y;
};
auto update = [&](auto self, int u, int l, int r, int pos) -> void{
if(l == r){
tr[u] += 1;
return;
}
if(pos <= mid)self(self, u << 1, l, mid, pos);
else self(self, u << 1 | 1, mid + 1, r, pos);
tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
};
auto query = [&](auto self, int u, int l, int r, int x, int y) -> int{
if(x <= l && y >= r){
return tr[u];
}
int res = 0;
if(x <= mid)res += self(self, u << 1, l, mid, x, y);
if(y > mid)res += self(self, u << 1 | 1, mid + 1, r, x, y);
return res;
};
// for(auto i : b)cout << i << " ";
// cout << "\n";
auto now = get(0);
update(update, 1, 1, siz, now);
for(int i = 1; i <= n; ++ i){
auto now = get(pre[i]);
update(update, 1, 1, siz, now);
auto need = pre[i] - k;
int l = 0, r = b.size() - 1, pos = -1;
while(l <= r){
if(b[mid] <= need){
pos = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
if(pos != -1)
ans += query(query, 1, 1, siz, 1, pos + 1);
}
cout << ans << "\n";
}