Count all subarrays satisfaying criteria

Problems and Contests
#1

Hello everyone! How can I count the number of sub-sections of an array where the maximum is X and the minimum is Y?

For example, given array [1, 5, 3, 1] X = 3, Y = 1. Answer will be 1. It’s only 1 sub-section [3, 1].

I need the solution with O(n) complexity.

I have gone through every sub-section length k (1 \leq k \leq n). But I need efficiency solution, please give me new ideas

#2

Is there a link to the actual problem on an OJ, or is this something you thought up?

#3

Sliding Window with 2 monotonic queue, one for maximum and the other is for minimum.

This is explained in USACO Guide.

1 Like