Auto comment: topic has been updated by CopeCope (previous revision, new revision, compare).

Let F(K) be the number of subsegments with the maximum element <= K (that is equivalent to the number of subsegments with all values smaller than or equal to K). Provided you can compute F, the answer would be F(K)-F(K-1).

In order to compute F, preprocess its values for numbers that appear in the array, that is F(a[i]). Sort the elements of the array and start with all of them "blocked". As you increase the current value for which you compute F, unblock elements: when you want to compute F(X) (for X some element of a), unblock occurrences of X one by one, so that in the end you'll have unblocked all numbers <= X. These unblocked numbers form continuous subsegments of various lengths. To each subsegment of length L, L(L+1)/2 subsegments with all numbers smaller than or equal to X will correspond. So what you need is a structure so that when you unblock an element you can compute the lengths of the continuous (maybe empty) unblocked subsegments that contained its neighbors. Let them be L1 and L2. From the current value subtract L1(L1+1)/2 and L2(L2+1)/2 and add (L1+1+L2)(L1+1+L2+1)/2 (for the newly formed subsegment). The current value will be, after unblocking all values of X, the value of F(X).

Now, when you have a query for K, you need to compute F(K) and F(K-1). In order to compute F(something) you need to find the largest value that appears in the array smaller than or equal to something and take the preprocessed value of F in that point (because between two As, F doesn't change as there is no new element that gets unblocked).

In the preprocess part you can use disjoint data set and would get complexity Nlog*N+NlogN+QlogN (because at each query you need to binary search the largest value of A smaller than or equal to K)

This idea follow somehow the same line of geniucos above, but I think is simpler.. Let a₁, a₂, ..., a_n the input array. Calculate for each index i to values l_i and r_i, where l_i is the first index j to the left of i such that a_j ≥ a_i. And r_i is the first index j to the right of i such that a_i < a_j. Some values of l_i can be 0, and some values of r_i can be n + 1. This values can be found in O(n) time using a stack, this is a fairly known algorithm. Each element a_i contribute to the answer for K = a_i in (i - l_i) × (r_i - i), so we can save this sums in a map for each value K. Then the queries are solved looking for the values in the map.

Can you provide the problem link, please?