## Ý tưởng chính
Ta cần đếm số lượng **dãy con liên tiếp** có tổng không nhỏ hơn `k`.
- Sử dụng **prefix sum** để tính nhanh tổng đoạn [l, r].
- Với mỗi chỉ số `r`, ta cần tìm **số lượng chỉ số `l`** sao cho:
$$
\text{prefix}[r] - \text{prefix}[l - 1] \ge k \\
\Leftrightarrow \text{prefix}[l - 1] \le \text{prefix}[r] - k
$$
- Ta duyệt từ trái sang phải, với mỗi `r`, dùng **tìm kiếm nhị phân** trong mảng `prefix[0..r-1]` để đếm bao nhiêu `prefix[i] ≤ prefix[r] - k`.
- Tổng hợp lại kết quả là số dãy con thỏa mãn yêu cầu.
⏱️ Độ phức tạp: **O(n log n)**
## Code mẫu
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define faster ios::sync_with_stdio(false); cin.tie(NULL);
int n;
ll k;
const int maxN = 1e5 + 1;
ll a[maxN];
ll prefix[maxN];
int main ()
{
faster;
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> a[i];
}
prefix[0] = 0;
for(int i = 1; i <= n; i++){
prefix[i] = prefix[i - 1] + a[i - 1];
}
ll res = 0;
for(int i = 1; i <= n; i++){
ll target = prefix[i] - k;
int l = 0, r = i - 1, pos = -1;
while(l <= r){
int mid = (r + l) / 2;
if(prefix[mid] <= target){
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if(pos != -1) res += (pos + 1);
}
cout << res << "\n";
return 0;
}
```
thor1407
Created at
0 likes