Overview

Given a sequence of positive integers \(A\) of length \(N\), this problem asks us to count the number of ways to either “remove nothing” or “remove a single contiguous interval \([l, r]\)” such that the sum of the remaining elements is exactly \(K\).

Analysis

Reformulation

Let \(S = \sum_{i=1}^N A_i\) be the total sum of all elements.

• If we do not cancel any days, the cost is \(S\) yen. We only need to determine whether this is equal to \(K\): if \(S = K\), there is \(1\) way; otherwise, \(0\) ways.
• If we cancel the interval \([l, r]\), the cost is \(S - \sum_{i=l}^r A_i\) yen. The condition for this to be equal to \(K\) is $\(\sum_{i=l}^{r} A_i = S - K\)$

In other words, letting \(T = S - K\), the problem reduces to “counting the number of intervals \((l, r)\) whose sum is exactly \(T\)”. This is a very standard problem.

Note that if \(T < 0\), this can never be achieved regardless of which interval is chosen (since \(A_i \ge 1\), every interval sum is strictly positive). Furthermore, if \(T = 0\), since \(A_i \ge 1\), an interval sum can never be \(0\), so there are \(0\) ways to cancel an interval (in this case, since \(S = K\), the only valid option is the \(1\) way of “not canceling any days”).

Issues with the Naive Approach

Checking all pairs \((l, r)\) exhaustively requires \(O(N^2)\) iterations, which amounts to roughly \(10^{12}\) operations for \(N \le 10^6\), making it too slow to pass within the time limit.

Another method is to compute prefix sums \(P_i = A_1 + \dots + A_i\) and count pairs satisfying \(P_r - P_{l-1} = T\) using an associative array (such as unordered_map). While this takes around \(O(N)\) time, using a hash table for \(N = 10^6\) incurs heavy constant-factor overhead and requires extra memory.

Solution: Two Pointers

The crucial observation here is the constraint that \(A_i \ge 1\) (all elements are positive). Because of this, for a fixed left endpoint \(l\), the interval sum \(\sum_{i=l}^{r} A_i\) is strictly increasing with respect to \(r\); and for a fixed right endpoint \(r\), increasing \(l\) causes the interval sum to strictly decrease.

Therefore, the “minimum \(l\) such that the interval sum is at most \(T\)” increases monotonically as \(r\) increases. Utilizing this monotonicity, we can count the intervals in linear time using the two pointers method.

Algorithm

1. Read the input and compute the total sum \(S\).
2. If \(S = K\), initialize the answer to \(1\) (the option to “not cancel any days”); otherwise, initialize it to \(0\).
3. Let \(T = S - K\). If \(T > 0\), count the number of intervals whose sum is \(T\) using the following two pointers method, and add it to the answer:
   • Initialize cur (the sum of the current window \([l, r]\)) to \(0\), and set l to the beginning.
   • Iterate r from \(0\) to \(N-1\):
     • cur += a[r]
     • While cur > T, execute cur -= a[l]; l++ (shrink the window from the left).
     • At this point, cur <= T. If cur == T, we have found exactly one valid interval ending at r, so increment the answer by \(1\).
4. Output the answer.

Note on Correctness

For each \(r\), there is at most one left endpoint \(l\) such that the sum equals \(T\) (because all elements are positive, making the sum strictly decreasing with respect to \(l\)). The pointer l after the loop is the “minimum \(l\) such that the sum of \([l, r]\) is at most \(T\)”, so if there exists an \(l\) whose sum equals \(T\), it must coincide with this l. Therefore, checking once for each \(r\) is sufficient.

Concrete Example

Consider \(N = 5\), \(A = (1, 2, 3, 4, 5)\), and \(K = 9\). Here, \(S = 15\) and \(T = 6\). The intervals with sum \(6\) are \([1, 3]\) (\(1 + 2 + 3\)) and \([3, 3]\)… not quite, since \(A_3 = 3\), and \([2, 3]\) is \(5\), while \([3, 4]\) is \(7\). In fact, only \((l, r) = (1, 3)\) works, which is \(1\) way. Since \(S \ne K\), the final answer is \(1\).

Complexity

• Time Complexity: \(O(N)\) (since r advances \(N\) times, and l also advances at most \(N\) times in total)
• Space Complexity: \(O(N)\) (to store the sequence; can be reduced to \(O(1)\) if elements are processed on the fly while reading)

Implementation Details

• Beware of overflow: \(S\) can be up to \(10^6 \times 10^9 = 10^{15}\) and \(K\) can also be up to \(10^{15}\), so the total sum, prefix sums, and cur must all be handled with 64-bit integers (long long). Using 32-bit int will definitely cause overflow.

• Do not forget the “do not cancel any days” case: This is counted separately from canceling an interval. When \(T = 0\) (\(S = K\)), since \(A_i \ge 1\), no interval has a sum of \(0\), so interval counting is unnecessary, and the answer is \(1\).

• When \(T < 0\): The answer is \(0\) (or just the result of the \(S = K\) check). It is safe to guard the loop so that it only runs when \(T > 0\).

• Fast I/O: Since \(N \le 10^6\), in C++ use scanf/printf, or include ios::sync_with_stdio(false); cin.tie(nullptr); when using cin. In Python, reading all input at once using sys.stdin.buffer.read() is essential.

• Adding the condition l <= r inside the inner while loop of the two pointers method helps safely prevent out-of-bounds indexing in general cases (in practice, since \(A_i \ge 1\) and \(T \ge 1\), whenever l > r we have cur = 0 \le T, so the loop terminates anyway).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; long long K;
    scanf("%d %lld", &n, &K);
    vector<long long> a(n);
    long long S=0;
    for(int i=0;i<n;i++){ scanf("%lld",&a[i]); S+=a[i]; }
    long long ans = (S==K)?1:0;
    long long T = S - K;
    if(T > 0){
        long long cur = 0;
        int l = 0;
        for(int r=0;r<n;r++){
            cur += a[r];
            while(cur > T && l <= r){ cur -= a[l]; l++; }
            if(cur == T) ans++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.