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

Can you answer these queries?
Автор AppleZ, 10 лет назад, По-русски

Okey,

We have N numbers (1 <= N <= 100000),

and gives Q questions L & R (1 <= Q <= 100000),

we must find I and J (can be empty) between L and R,

that sum between I and J maximal,

and we must counted one number one times

Example:

INPUT:

9

{ 4, -2, -2, 3, -1, -4, 2, 2, -6 }

3

1 2

1 5

4 9

OUTPUT:

4

5

3

You can found problem here

Thank you

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use segment tree. And for each vertex you should save sum on whole segment, maximal sum on prefix, maximal sum on suffix, maximal sum on subarray. Then on each level you easily change that. And answer can find easily too.

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

Google "can you answer these queries ii". There is some blog's posts about, but I did not found any good explanation. Maybe there is good one in chinese, but I can't understand google-translated text.
First note answer(x, y) is equal to max(answer2(x, y), answer2(x + 1, y),...,(answer2(y, y)). Asnwer2 is max(sumOfSubarray(x, y), sumOfSubarray(x + 1, y),..., sumOfSubarray(y, y)). SumOfSubarray counted one number one time. I have found scan-line NLogN solution used this notice, but i did not understand it well to explain.

→ Ответить