\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày Trâu> <Quy hoạch động>}}\)

• Duyệt qua các đoạn \([i, j]\) với (\(1 \leq i \leq j \leq n\))

Với mỗi đoạn ta tính tổng \(S\) và tăng biến đếm nếu \(S = k\)

• Độ phức tạp tổng thể là $O(n^2) \times \(O(calculate)\)

Cày trâu: Ta tính lại từng đoạn \([i, j]\) tổng \(S\) thì \(O(calculate) = O(j - i + 1) = O(n)\)

Quy hoạch động trực tiếp: Ta sử dụng kết quả \(S\) từ đoạn \([i, j)\) và thêm \(a[j]\) vào \(S\). Ta có thể tính được đoạn hiện tại từ đoạn trước trong \(O(calculate()) = O(1)\)

Quy hoạch động tiền xử lí: Ta sẽ dùng mảng cộng dồn, với \(f[l..r]\) là tổng các số trong đoạn \([l, r]\)

Công thức quy hoạch động:

\(f[0..0] = 0\)

\(f[0..n] = f[0..n - 1] + a[n]\)

\(f[l..r] = f[0..r] - f[0..l - 1]\)

Vậy sau khi tiền xư lí các \(f[0..n]\) trong \(O(n)\) ta có thể tính được giá trị đoạn \([l, r]\) trong \(O(calculate()) = O(1)\)

\(\color{#300000}{\text{Hint 2 <Mảng tần số> <STL> <Hash>}}\)

• Khi duyệt đến \(i\) ta sẽ tăng tần số xuất hiện của tổng \(S = \overset{n}{\underset{j = 1}{\Sigma}} a_j\) trong mảng \(fre[]\) lên

Trước khi tăng biến đếm, ta sẽ cộng vào số đoạn con có giá trị \(S - k\)

Chứng minh: nếu có ít nhất một đoạn con có giá trị \(S - k\), mà giá trị của cả mảng đang xét hiện tại là \(S\), thì sau khi loại bỏ đoạn con này, phần còn lại sẽ có tổng là \(k\)

Và hiển nhiên ta tăng biến đếm khi \(S = k\)

• Lưu ý trong trường hợp số \(S - k\) âm thì ta có 4 cách xử lí

Dùng một mảng tần số các số dương, một mảng tần số các số âm

Dùng một mảng con trỏ để trỏ tới các giá trị dương, và lúc này vẫn có thể sài con trỏ âm được

Dịch mảng lên một giá trị bằng \(max\_k\) và xét trên đoạn \([0.. 2 \times max_k + 1]\)

Sử dụng \(STL\) và dùng \(std::unordered\_map\) với độ phức tạp là \(O(1)\) cho viêc kiểm tra kể cả số âm

\(\color{#009933}{\text{Preference Accepted Code }}\): Mảng tần số, STL

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n, k;
    cin >> n >> k;

    ll sum = 0;
    ll res = 0;
    unordered_map<int, int> fre;
    while (n--)
    {
        int x;
        cin >> x;
        sum += x;
        if (sum == k) res++;
        res += fre[sum - k];
        fre[sum]++;
    }

    cout << res;
    return 0;
}