# Dãy con

# Đề bài
*Những dữ kiện trong đề bài và cách diễn đạt đều được viết lại so với đề gốc. Tụi mình rất mong nhận được phản hồi của các bạn nếu phát hiện sai sót.*

Cho dãy số $a$ độ dài $n$ chỉ gồm các số nguyên dương không quá $10^9$ và một số nguyên dương $k$ ($a_i \leq 10^9,\ k \leq 10^9$).

Một dãy số $b$ được gọi là dãy con của $a$ nếu như $b$ có thể được tạo ra bằng cách xóa đi một vài phần tử **liên tiếp** ở đầu và cuối dãy số $a$ (có thể không xóa phần tử nào). Theo định nghĩa này, $a$ cũng là dãy con của chính nó.

## **Yêu cầu**

Hãy đếm số dãy con của $a$ sao cho $sum$ (tổng của mọi phần tử trong dãy con đó) không bé hơn $k$ ($sum \geq k$).
## **Input**
Vào từ tệp văn bản **DAYCON.INP** gồm:

- Dòng đầu tiên gồm hai số nguyên dương $n$ và $k$ ($1 \leq n \leq 10^6$, $1 \leq k \leq 10^9$), lần lượt là kích thước dãy số $a$ và số $k$ trong mổ tả đề bài.
- Dòng thứ hai gồm $n$ số nguyên dương $a_i$ ($1 \leq a_i \leq 10^7$), các phần tử của dãy số $a$.
## **Output**
Đưa ra tệp văn bản **DAYCON.OUT** một số nguyên không âm duy nhất là số
dãy con của $a$ thỏa điều kiện trên.

## **Scoring**

| **Subtask** | **Điểm** | **Giới hạn**|
| ------------- | ---------- | ---------------|
| $1$ | $60$ | $n \leq 100$|
| $2$ | $30$ | $n \leq 10^3$|
| $3$ | $10$ | $n \leq 10^6$|

## **Example**
| DAYCON.INP | DAYCON.OUT |
| ------------- | ---------- |
| 5 6 <br> 1 2 1 4 5 | 6 |
## **Notes**
Trong test ví dụ trên, có $6$ dãy con của $a$ có tổng không bé hơn $k$ là:

- $\{1, 2, 1, 4 \}$

- $\{ 1, 2, 1, 4, 5 \}$

- $\{2, 1, 4 \}$

- $\{2, 1, 4, 5 \}$

- $\{1, 4, 5 \}$

- $\{4, 5 \}$

# Solution

## Prerequisites

Hai con trỏ, tìm kiếm nhị phân, mảng cộng dồn.

## **Subtask 1**: $n \leq 100$

Trong subtask này, ta sẽ duyệt qua mọi dãy con của $a$ trong $O(n ^ 2)$ với $2$ vòng for lồng nhau và tính tổng của chúng trong $O(n)$ cho từng dãy con. Với mỗi dãy con, nếu tổng của chúng lớn hơn hoặc bằng $k$ thì ta sẽ tăng đáp án lên $1$.

Độ phức tạp: $O(n ^ 3)$.

## **Subtask 2**: $n \leq 10^3$

Thật ra, độ phức tạp thực tiễn của thuật toán cho subtask $1$ của chúng ta rất nhanh, khi các vòng for chỉ lặp $160$ triệu lần. Do đó, code của subtask $1$ nhiều khả năng sẽ qua được test của subtask $2$; tuy nhiên, chúng mình vẫn sẽ nói về thuật toán chuẩn cho subtask $2$ ở phần tiếp theo.

Ta nhận xét rằng, thay vì tính lại tổng từ đầu sau mỗi lần ta tăng biên phải lên $1$ thì ta chỉ cần thêm giá trị của biên phải vừa thêm vào tổng cũ và làm tương tự như subtask $1$. Từ đó, ta có thể lược bỏ được bước duyệt $O(n)$ để tính tổng, tối ưu được thuật toán xuống $O(n^2)$.

Độ phức tạp: $O(n ^ 2)$.

## **Subtask 3**: $n \leq 10^6$

Để làm được bài toán với ràng buộc này, chúng ta cần phải sử dụng kỹ thuật hai con trỏ hoặc tìm kiếm nhị phân để tối ưu bước duyệt các dãy con.

### **Lời giải 1: Tìm kiếm nhị phân**

Ta sẽ duyệt qua mọi vị trí $r$, biên phải của các dãy con ta đang xét.

Ta nhận xét rằng, với một biên $r$ cố định, nếu ta tìm được vị trí biên trái $l$ sao cho tổng của dãy con từ $l$ tới $r$ lớn hơn hoặc bằng $k$ thì mọi dãy con có vị trí biên phải $l' \leq l$ và biên trái $r$ đều thỏa mãn điều kiện trên.

Để chứng minh nhận xét trên, ta gọi $sum_{l, r}$ là tổng của dãy con có biên trái $l$ và biên phải $r$. Ta nhận thấy được $sum_{l', r} = sum_{l', l - 1} + sum_{l, r}$, mà do các phần tử của $a$ đều dương nên $sum_{l', l - 1}$ luôn không âm. Vì thế nên $sum_{l', r} \geq sum_{l, r} \geq k$, thỏa điều kiện ta muốn chứng minh.

Do đó, với một vị trí biên phải $r$, ta chỉ quan tâm đến vị trí biên phải $l$ lớn nhất sao cho dãy con có biên trái $l$ và biên phải $r$ có tổng lớn hơn $k$. Ta có thể sử dụng thuật toán tìm kiếm nhị phân kêt hợp với mảng cộng dồn để làm được điều này trong $O(\log n)$. Gọi $l$ là vị trí của biên trái lớn nhất thỏa điều kiện với biên phải $r$. Do mọi biên trái $l' \leq l$ đều thỏa nên đáp án của chúng ta sẽ tăng lên $l$. Vì ta duyệt qua mọi biên phải nên độ phức tạp thuật toán của chúng ta là $O(n \times \log n)$.

Độ phức tạp : $O(n \times \log n)$.

### **Lời giải 2: Hai con trỏ**

Ta sử dụng nhận xét tương tự như solution sử dụng tìm kiếm nhị phân. Tuy nhiên, ta nhận ra thêm một điều nữa là khi ta duyệt biên phải $r$ tăng dần, vị trí biên trái $l$ lớn nhất thỏa yêu cầu cũng sẽ không giảm.

Chứng minh: Gọi $r_1, r_2$ là hai vị trí biên phải ta duyệt qua. Không mất tính tổng quát ta giả sử $r_1 < r_2$. Định nghĩa $f(r)$ là hàm trả về vị trí biên trái lớn nhất thỏa yêu cầu đề bài khi nhận vào giá trị biên phải $r$.

Ta cần chứng minh $f(r_1) \leq f(r_2)$. Thật vậy, nếu dãy con có biên trái $f(r_1)$ và biên phải $r_1$ thỏa yêu cầu tổng lớn hơn hoặc bằng $k$ thì vị trí này cũng sẽ thỏa với biên phải $r_2$ do $sum_{f(r_1), r2} = sum_{f(r_1), r_1} + sum_{r_1, r_2}$, mà $sum_{r1, r2}$ dương nên ta có $sum_{f(r_1), r2} > sum_{f(r_1), r_1}$.
Vì thế nên $f(r_2) \leq f(r_1)$, ta có điều ta cần chứng minh.

Có những điều trên, ta sẽ lưu biên trái $l$ lớn nhất thỏa điều kiện khi ta đang duyệt qua biên phải $r$ và cập nhật đáp án tương tự như lời giải sử dụng tìm kiếm nhị phân.

Độ phức tạp : $O(n)$

Code mẫu:

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;  

int n, k, a[N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("DAYCON.inp", "r", stdin);
    freopen("DAYCON.out", "w", stdout);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int l = 1;
    long long sum = 0;
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        sum += a[i];
        while(sum >= k){
            sum -= a[l];
            l++;
        }
        ans += l - 1;
    }
    cout << ans << "\n";
    return 0;
}