Distinct Subarrays with Bounded Sum
Given an array of N integers A and two integers L and R. Count the number of distinct subarrays of A whose sum S satisfies L <= S <= R.
Input
The first line contains three integers N, L, R. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer representing the count of distinct subarrays satisfying the condition.
Constraints
1 <= N <= 200000, 0 <= L <= R <= 10^14, 1 <= A_i <= 10^9.
Example 1
3 3 7 1 2 3
4
Subarrays are [1,2](sum=3), [1,2,3](sum=6), [2,3](sum=5), [3](sum=3). All sums are between 3 and 7. Count is 4.
Example 2
5 10 20 5 3 7 2 8
7
Subarrays: [5,3,7](sum=15), [7,2,8](sum=17), [5,3,7,2](sum=17), [3,7,2,8](sum=20), [5,3,7,2,8](sum=25 not in range). Valid sums are 15, 17, 17, 20. Count is 4.
Hints
Similar problems
- Longest Subarray with Distinct ElementsHard
- Longest Subarray with Equal Number of Zeroes and OnesHard
- Pairs with Same ParityMedium
- Count Unique Element PairsMedium
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with At Most K Distinct ElementsMedium
More topics: Hash Map and Hashing problems, Two Pointers problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 3 7 1 2 3
5 10 20 5 3 7 2 8