给你两个序列 \(a\)、\(b\) 和 \(S\)，求满足一下条件的区间 \([l ,r]\) 的数量：
- \(\sum_{i = l}^r b_i + \min_{i = l}^r a_i \le S\)。
\(n \le 2 \times 10^5\)。
考虑按最小值分治，即分治中心 \(mid\) 是区间 \([l, r]\) 的区间最小值的位置，这个分治中心可以用 ST 表来找，这样区间的最小值就是 \(a_{mid}\)，现在就只要求跨过分治中心的满足 \(b\) 的和小于等于 \(S - a_{mid}\) 的区间数量就行了。
如果我们确定了一个断点，由于 \(\sum b\) 是单调的，就可以通过二分找到另一个端点的取值范围。所以按分治中心将当前的区间划分成两部分，然后枚举较短的一边的，在较长的一边二分。
时间复杂度 \(O(n \log^2 n)\)。
constexpr int MAXN = 2e5 + 9, MAXLG = 18;
int n;
ll S, a[MAXN], b[MAXN], ans = 0;
pli st[MAXLG][MAXN];
pli Query(int l, int r) {
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
void Solve(int l, int r) {
if (l > r) return;
int mid = Query(l, r).sec;
if (mid - l < r - mid) {
for (int i = l; i <= mid; i ++) {
ll s = S - (b[mid] - b[i - 1]) - a[mid] + b[mid];
int L = mid, R = r;
while (L < R) {
int Mid = L + R + 1 >> 1;
if (b[Mid] <= s) L = Mid;
else R = Mid - 1;
}
if (b[L] <= s) ans += L - mid + 1;
}
} else {
for (int i = mid; i <= r; i ++) {
ll s = (b[i] - b[mid]) + a[mid] + b[mid] - S;
int L = l, R = mid;
while (L < R) {
int Mid = L + R >> 1;
if (b[Mid - 1] >= s) R = Mid;
else L = Mid + 1;
}
if (b[L - 1] >= s) ans += mid - L + 1;
}
}
Solve(l, mid - 1), Solve(mid + 1, r);
return;
}
void slv() {
n = Read<int>(), S = Read<ll>();
for (int i = 1; i <= n; i ++) a[i] = Read<ll>();
for (int i = 1; i <= n; i ++) b[i] = Read<ll>() + b[i - 1];
for (int i = 1; i <= n; i ++) st[0][i] = {a[i], i};
for (int i = 1; i <= __lg(n); i ++) for (int j = 1; j + (1 << i) - 1 <= n; j ++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
Solve(1, n);
Write(ans, '\n');
return;
}