logoChat01.ai

You are given an array of integers a1,a2,…,an and...

Created on: June 17, 2025

Answered using O4 Mini High by Chat01

Question

You are given an array of integers a1,a2,…,an
and two integers s
and x
. Count the number of subsegments of the array whose sum of elements equals s
and whose maximum value equals x
.

More formally, count the number of pairs 1≤l≤r≤n
such that:

al+al+1+…+ar=s
.
max(al,al+1,…,ar)=x
.
Input
Each test consists of multiple test cases. The first line contains a single integer t
(1≤t≤104
) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers n
, s
, and x
(1≤n≤2⋅105
, −2⋅1014≤s≤2⋅1014
, −109≤x≤109
).

The second line of each test case contains n
integers a1,a2,…,an
(−109≤ai≤109
).

It is guaranteed that the sum of n
across all test cases does not exceed 2⋅105
.

Output
For each test case, output the number of subsegments of the array whose sum of elements equals s
and whose maximum value equals x
.

Example
InputCopy
9
1 0 0
0
1 -2 -1
-2
3 -1 -1
-1 1 -1
6 -3 -2
-1 -1 -1 -2 -1 -1
8 3 2
2 2 -1 -2 3 -1 2 2
9 6 3
1 2 3 1 2 3 1 2 3
13 7 3
0 -1 3 3 3 -2 1 2 2 3 -1 0 3
2 -2 -1
-2 -1
2 -2 -1
-1 -2
OutputCopy
1
0
2
0
2
7
8
0
0
Note
In the first test case, the suitable subsegment is l=1
, r=1
.

In the third test case, the suitable subsegments are l=1
, r=1
and l=3
, r=3
.

In the fifth test case, the suitable subsegments are l=1
, r=3
and l=6
, r=8
.

In the sixth test case, the suitable subsegments are those for which r=l+2
.

In the seventh test case, the following subsegments are suitable:

l=1
, r=7
.
l=2
, r=7
.
l=3
, r=6
.
l=4
, r=8
.
l=7
, r=11
.
l=7
, r=12
.
l=8
, r=10
.
l=9
, r=13
.
code this in java

Thought

Planning algorithm approach

I’m thinking we need an efficient way to count subarrays where the sum equals s and the maximum equals x. Since we’re dealing with large input sizes (up to 200,000 elements), the solution needs to be within O(n) or O(n log n) per test case. Hmm, to solve this, we can focus on subarrays that contain x as the maximum, make sure no elements exceed x, and the sum is exactly s. I’ll need to figure out how to efficiently track the sum and maximum as I slide through the array.

Counting valid subarrays

We need to count subarrays where all elements are ≤ x, at least one element equals x, and the sum equals s. To do this, I can split the array into blocks where each element is ≤ x. Any element greater than x splits these blocks, as it would violate the "max equals x" condition. For each block, I'll count subarrays with sum = s and containing at least one x. I'll approach this by first counting all subarrays with sum = s, then subtracting those that don’t contain x.

Implementing the approach

We need to handle cases where s could be negative and use long for the sums. The total n across test cases can be up to 200,000, so we need an efficient solution. Prefix sums and a hash map will be key. For each block (where elements are ≤ x), we count subarrays with sum s using the hash map; subarrays without x will be counted separately. The time complexity should be O(n) for each case. I'll write the code skeleton in Java, using fast I/O and proper types like long.

Thought for 18 seconds

Answer

Here’s an O(n)O(n)-time solution per test case using the “split on >x” + prefix-sum + hash-map trick:

java
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long S = Long.parseLong(st.nextToken());
            long X = Long.parseLong(st.nextToken());
            long[] a = new long[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(st.nextToken());
            }

            long ans = 0;
            int segmentStart = 0;
            // break the array into segments where all a[i] <= X
            for (int i = 0; i <= n; i++) {
                if (i == n || a[i] > X) {
                    // process [segmentStart .. i-1]
                    ans += countTotal(a, segmentStart, i, S)
                         - countWithoutX(a, segmentStart, i, S, X);
                    segmentStart = i + 1;
                }
            }

            out.println(ans);
        }
        out.flush();
    }

    // count all subarrays in a[l..r-1] with sum == S
    static long countTotal(long[] a, int l, int r, long S) {
        Map<Long, Long> freq = new HashMap<>();
        freq.put(0L, 1L);
        long pref = 0, cnt = 0;
        for (int i = l; i < r; i++) {
            pref += a[i];
            cnt += freq.getOrDefault(pref - S, 0L);
            freq.put(pref, freq.getOrDefault(pref, 0L) + 1);
        }
        return cnt;
    }

    // count all subarrays in a[l..r-1] with sum == S that contain NO element == X
    // (i.e. split again at positions where a[i]==X)
    static long countWithoutX(long[] a, int l, int r, long S, long X) {
        long cnt = 0;
        int subStart = l;
        for (int i = l; i <= r; i++) {
            if (i == r || a[i] == X) {
                cnt += countTotal(a, subStart, i, S);
                subStart = i + 1;
            }
        }
        return cnt;
    }
}

How it works

  1. Split on “too large”: Any element >x>x can’t appear in a valid segment, so we break the array into maximal chunks of elements ≤x\le x.
  2. Total vs. no-xx: Within each chunk, the number of subarrays summing to ss and having max⁡=x\max=x equals (#subarrays with sum s)−(#subarrays with sum s and no element =x). (\#\text{subarrays with sum }s) -(\#\text{subarrays with sum }s\text{ and no element }=x).
  3. Prefix-sum + hash-map: We count how many subarrays sum to ss by maintaining a running prefix sum and a map freq of “how many times each prefix sum has occurred.”

This runs in O(n)O(n) per test, and handles negatives, large sums, and up to 2×1052\times10^5 total elements across all tests.

Share this Q&A