\(\Large\textbf{Solution: } \large{感觉是特别经典的一类题目啊,有多种方法,先介绍一种以后再写。\\题目的要求其实就是求sum[i] - sum[j] < t的区间个数,其中sum[i]表示到i的前缀和。\\移项式子为sum[j] > sum[i] + t,发现和逆序对很像,所以考虑归并排序统计答案。}\)
\(\Large\textbf{Summary: } \large{如果题目要求可以转换为像本题的区间关系,可以考虑线段树、树状数组、归并等来计算答案。}\)
\(\Large\textbf{Code: }\)
#include <bits/stdc++.h>
#define gc() getchar()
#define LL long long
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
const int N = 2e5 + 5;
const int inf = 0x7fffffff;
int n;
LL m, ans, a[N];
inline LL read() {
LL x = 0; int flg = 1;
char ch = gc();
while (!isdigit(ch)) {
if (ch == '-') flg = -1;
ch = gc();
}
while (isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
return x * flg;
}
inline void Merge(int l, int r) {
int mid = (l + r) >> 1, i = l, j = mid + 1;
if (l == r) return;
Merge(l, mid); Merge(mid + 1, r);
while (i <= mid && j <= r)
if (a[j] - a[i] >= m) ++i;
else ans += mid - i + 1, ++j;
inplace_merge(a + l, a + mid + 1, a + r + 1);
return;
}
int main() {
ios::sync_with_stdio(false);
n = read(), m = read();
rep(i, 1, n) a[i] = read() + a[i - 1];
Merge(0, n);
cout << ans << endl;
return 0;
}