AppleZ's blog

Can you answer these queries?
By AppleZ, 10 years ago, In Russian

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you know russian, you can read it here.

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

      Thank you, but can you explain me what we must to do with NUMBER which found two or more times?

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

        I'm sorry. I don't read the whole statement.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply