CopeCope's blog

By CopeCope, history, 6 years ago, In English

Given array A of N (N <= 106 ) elements (Ai <= 109 ). Given Q queries (Q <= 106 ). Every query consist of number K (K <= 109 ). 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]

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
Rev. 4   Vote: I like it +20 Vote: I do not like it

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)

»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

This idea follow somehow the same line of geniucos above, but I think is simpler.. Let a1, a2, ..., an the input array. Calculate for each index i to values li and ri, where li is the first index j to the left of i such that aj ≥ ai. And ri is the first index j to the right of i such that ai < aj. Some values of li can be 0, and some values of ri can be n + 1. This values can be found in O(n) time using a stack, this is a fairly known algorithm. Each element ai contribute to the answer for K = ai in (i - li) × (ri - 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide the problem link, please?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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