kitesho's blog

[Help] Segment tree: Maximum over range with additional constraints.
By kitesho, 3 years ago, In English

You are given an array A of size N. For each prefix of the A, you have to calculate the value described in the below function.

int func(){
    int ans = 0;
    for(int i = 0; i <= prefix_index; i++){
        int c = 0;
        for(int j = 0; j <= prefix_index; j++){
              if(A[j] >= A[i]) c++;
        }
        ans = max(c * A[i], ans);
    }
    return ans;
}

i.e., in a prefix, the value for the index i is, number of elements greater than or equal to A[i] * A[i]. The answer for the prefix is maximum of these values. The output is a list of N numbers (one for each prefix).

constraints:
1 <= N <= 150000
1 <= A[i] <= 1e9

sample test case:
A = [10, 11, 12, 10, 11, 50, 70]
ans: [10, 20, 30, 40, 50, 60, 100]

test case explanation

I believe this can be solved using segment tree. Solutions without using segment tree will be also interesting. But want to know how to solve using segment tree.

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
int main(){
    int ans = 0;
    tree = empty();
    for(int i = 0; i <= n; i++){
        int c = tree.querySum(a[i]..max);
        tree.update(a[i], +1);
        ans = max(c * A[i], ans);
        cout << ans << ' ';
    }
}
→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +24 Vote: I do not like it

    Is your approach, calculate value at an index i and compare the value with the previous ans?

    But the element at this index can affect ans calculated before.

    → Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I think the following idea works: maintain a fenwick tree on values initialized with 0. now iterate from left to right at each index the value for this index is prefix_sum of (A[i]-1)*(A[i]) this prefix sum can be calculated in logn time with fenwick tree After processing this index add 1 to A[i] in fenwick tree Now problem boils down to basic prefix minimum queries which can be solved easily.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Is your approach, fenwick tree to calculate the number of elements greater than or equal to A[i] (lets call this count as c) and multiply it with A[i]?

    lets assume we updated the fenwick tree and calculated the answer for prefix ending at i. for the prefix i+1, if we add the A[i+1] in the tree, it will change the "c" of elements less than or equal to A[i+1] and that will change the value c*A[j] (j from 0 to i, where A[j] <= A[i+1]). In that case, we should calculate again for prefix ending at i.
    wouldn't it lead to n^2 solution?

    → Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

What are the constraints on N and the values in A?

→ Reply