Given array A of N (N <= 10^{6} ) elements (Ai <= 10^{9} ). Given Q queries (Q <= 10^{6} ). Every query consist of number K (K <= 10^{9} ). For every query find number of subsegments such that their maximum element is K.

Test case:

5

1 2 3 4 3

3

2

3

4

Output:

2 -> [2], [1,2]

4 -> [1,2,3], [2,3], [3], [3]

8 -> [1,2,3,4], [1,2,3,4,3], [2,3,4], [2,3,4,3], [3,4], [3,4,3], [4], [4,3]

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_{1},a_{2}, ...,a_{ n}the input array. Calculate for each indexito valuesl_{ i}andr_{ i}, wherel_{ i}is the first indexjto the left ofisuch thata_{ j}≥a_{ i}. Andr_{ i}is the first indexjto the right ofisuch thata_{ i}<a_{ j}. Some values ofl_{ i}can be 0, and some values ofr_{ i}can ben+ 1. This values can be found inO(n) time using a stack, this is a fairly known algorithm. Each elementa_{ i}contribute to the answer forK=a_{ i}in (i-l_{ i}) × (r_{ i}-i), so we can save this sums in a map for each valueK. Then the queries are solved looking for the values in the map.Can you provide the problem link, please?

Well, it is written on Serbian but you can submit it anyways (you need to register, upper-right corner) Submit