[Help] Segment tree: Maximum over range with additional constraints.

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

for prefix 1 to 1

for prefix 1 to 2

for prefix 1 to 3

for prefix 1 to 4

for prefix 1 to 5

for prefix 1 to 6

for prefix 1 to 7

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.

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 << ' '; } }

Комментарии (8)

Написать комментарий?

vstiff

11 месяцев назад, # |

→ Ответить

kitesho

11 месяцев назад, # ^ |

+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.

← Rev. 2 →

That's interesting then. Share your solution if you'll solve it.

Sounds like Li-Chao tree under Problem 2 section.

Dr.CHAMPIONSTEIN

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.

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?

I am sorry I misinterpreted the question

I apologize

EMBailey

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

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