题面
有一个长度为 \(n\) 的序列 \(a\) 和一个数 \(t\)，求有多少个区间 \([l,r]\) 满足 \(a_{l}+a_{l+1}+...+a_{r}<t\)。\((n\le 2×10^5,|t|\le 2×10^{14},|a_i|\le 10^9)\)
题解
将题目转化为“求有多少对 \(l,r\) 满足 \(S_r-S_l<t\)"，其中 \(S\) 为前缀和，\(l\in [0,n-1],r\in [1,n]\)。
法1：CDQ分治
当分治到 \([l,r]\) 时
- 递归求解 \([l,mid]\) 与 \([mid+1,r]\)。
- 此时 \([l,mid]\) 与 \([mid+1,r]\) 是有序的，用双指针求出 \([l,r]\) 的答案。
- 将区间 \([l,r]\) 排序。
#include<bits/stdc++.h>
#define int long long
const int maxn = 2e5 + 5;
int n, t, a[maxn], S[maxn];
int ans = 0;
void solve(int l, int r) {
if(l == r) return ;
int mid = (l + r) >> 1;
solve(l, mid); solve(mid + 1, r);
int L = l, R = mid + 1;
while(L <= mid && R <= r) {
if(S[L] + t <= S[R]) {
++L;
}
else {
ans += mid - L + 1;
++R;
}
}
std::sort(S + l, S + r + 1);
}
signed main() {
std::ios::sync_with_stdio(0); std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> t;
for(int i = 1; i <= n; ++i) {
std::cin >> a[i];
S[i] = S[i - 1] + a[i];
}
solve(0, n);
std::cout << ans;
return 0;
}