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

Please help me solve this problem!
Автор nguyenmanhthien98, 10 лет назад, По-английски

Give a sequence a[1], a[2], ..., a[n] (|a[i]| <= 15000, n <= 50000). Let function q(x, y) = max { sum(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }. There are m query form x y (1 <= x <= y <= n). (m <= 50000) calculate q(x, y)

Sorry for my bad English.

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

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

can you give problem's link ?

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

Suppose for 2 given ranges (x, y) and (y+1, z) you know these things:
Maximum subarray starting at x and at y+1
Maximum subarray ending at y and at z.
Maximum subarray that lies completely within the intervals (x, y) and (y+1, z).
Total Sum of range (x, y) and (y+1, z).
Now, try calculating the same things for the range (x, z) using these 8 values.
Once you are done, you can make a segment tree storing these values to give you the answer.

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

The solution to this problem is discussed here. The tutorial is written in Russian, use Google for translating.

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

You could find standard segment tree solution from lots of places, I would like to introduce a new solution under the constraints of this problem.

You can split queries into buckets by their x's. We will calculate answers for each of bucket separately.

Sort all of the queries of current bucket by theirs end points. As you see starts point can change only . End points are increasing, so you can calculate maximum sum interval lies between maximum start point and current end point. Also you can calculate max sum lies at left part with bruteforce O(N). One more thing, left optimal answer's start point can be at left part and endpoint at right part. This time one can just calculate maximum prefix sum of right part and minimum prefix sum of left part. Their difference equals maximum sum of last case.

Overall complexity is

I will add some visual samples soon. Feel free to ask any questions.

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

    Thanks, but the time limit is 0.09s...

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

      It still has chance because constant factor is too little. I will implement it and share results if get accepted.

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

      Firstly test set has huge inputs with M > 105.

      Secondly time limit is not 0.09 seconds it is 0.23 seconds.

      Fortunalty my still gets AC with 0.19 secs which means 404th rank at best solutions list.(There are 5000 accepted solutions)

      Here is the link to the implementation

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

I've solved it with segment tree. In each node you need to store the maximum sum starting with the leftmost element, the maximum sum starting with the rightmost element, the maximum sum of consecutive elements in the interval and the total sum. In my solution the variable indicator shows me if the total sum is equal to the maximum sum.

My solution

Ask if you didn't understand something.

→ Ответить