题意
给定一个长度为 n 的整数数列 $a_1,a_2,…,a_n$ 和一个整数 $t$。
请你判断共有多少个数对 $(l,r)$ 同时满足:
- $1≤l≤r≤n$
- $\Sigma_{i = l}^{r} a_i < t$
题解
首先应该不难想到定义前缀和 $s_k = \Sigma_{i = 0}^{k} a_i, a_0 = 0$,那么题目条件就可以修改成 $s_r - s_{l - 1} < t$,也就等价于 $s_{l - 1} > s_r - t$。
那么就相当于每一次固定$s_r$,求有多少 $l - 1 \in [0, r - 1]$ 满足 $s_{l - 1} > s_r - t$
这样实际上每次询问就是求一个给定区间的元素有多少。对于这个问题,我们应该想到用线段树来维护某个区间范围内的元素个数,但是需要注意所有的元素范围太大了,需要去重离散化。
那么问题实际上就是遍历之后每次先区间查询,然后单点修改。代码如下。
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2022-03-20
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
ll n, t, a[maxn], pre[maxn], ans = 0;
ll init_a[maxn];
vector<ll> vec;
int find_rank(ll x){
return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define father(x) ((x) >> 1)
struct seg_node{
int sum, left, right;
int lazy;
};
struct seg_tree{
public:
seg_node tree[4 * maxn];
void Pushup(int k){
tree[k].sum = tree[lson(k)].sum + tree[rson(k)].sum;
}
void build(int left, int right, int k = 1){
tree[k].left = left, tree[k].right = right;
if (left == right){
tree[k].sum = init_a[left];
return;
}
int mid = (left + right) >> 1;
build(left, mid, lson(k));
build(mid + 1, right, rson(k));
Pushup(k);
}
void Pushdown(int k){
if (tree[k].lazy == 0) return;
tree[lson(k)].lazy += tree[k].lazy, tree[rson(k)].lazy += tree[k].lazy;
tree[lson(k)].sum += tree[k].lazy * (tree[lson(k)].right - tree[lson(k)].left + 1);
tree[rson(k)].sum += tree[k].lazy * (tree[rson(k)].right - tree[rson(k)].left + 1);
tree[k].lazy = 0;
}
void Update_seg(int l, int r, int x, int y, int C, int k = 1){
if (x <= l && r <= y){
tree[k].sum += (r - l + 1) * C;
tree[k].lazy += C;
return;
}
Pushdown(k);
int mid = (l + r) >> 1;
if(x <= mid) Update_seg(l, mid, x, y, C, lson(k));
if(y > mid) Update_seg(mid + 1, r, x, y, C, rson(k));
Pushup(k);
}
int Query_seg(int l, int r, int x, int y, int k = 1){
int ret = 0;
if (x <= l && r <= y){
ret = tree[k].sum;
return ret;
}
Pushdown(k);
int mid = (l + r) >> 1;
if (mid >= x) ret += Query_seg(l, mid, x, y, lson(k));
if (mid < y) ret += Query_seg(mid + 1, r, x, y, rson(k));
return ret;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> t;
vec.push_back(0);
for (int i = 1; i <= n; i++){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
vec.push_back(pre[i]), vec.push_back(pre[i] - t);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
seg_tree st;
st.build(1, vec.size());
st.Update_seg(1, vec.size(), find_rank(0), find_rank(0), 1);
for (int i = 1; i <= n; i++){
int tmp = 0, nowq_rk = find_rank(pre[i] - t);
if(nowq_rk + 1 <= vec.size()) tmp = st.Query_seg(1, vec.size(), nowq_rk + 1, vec.size());
ans += tmp;
int nowupd_rk = find_rank(pre[i]);
st.Update_seg(1, vec.size(), nowupd_rk, nowupd_rk, 1);
}
cout << ans << endl;
return 0;
}