Блог пользователя kitesho

[Help] Segment tree: Maximum over range with additional constraints.
Автор kitesho, 10 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
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 << ' ';
    }
}
→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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.

    → Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить