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

Автор solaimanope, история, 5 лет назад, По-английски

You start with an array containing all zeroes. You will be given some updates. Updates are in the form $$$L, R, A, B$$$. For each update, you have to add $$$A+(i-L)*B$$$ for each $$$L \leq i \leq R$$$. You will have to answer queries in the form $$$L, R$$$. For each query, you have answer what's the maximum element in $$$[L, R]$$$ range.

The range sum query version of this problem can be solved with segment tree with lazy propagation. However, I can't think of a way to solve this one.

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

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

Problem link please?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

Maybe lichao tree? I don't have a idea.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

This can be solved with normal sqrt decomposition.

For each query $$$L, R, A, B$$$, lets say that $$$A - L * B$$$ as a const value and now the remain problem is only adding $$$i * B$$$. If we assume that each element is a line with slope $$$i$$$ then the problem become finding $$$max(f(i) = i$$$ * (sum of B + const values that have been updated on it $$$))$$$.

Assume that before each query, we have built a convex hull for each blocks. If the current query only conflicts but not covers a block, just update all the element in that block and build its convex hull again. Or else, simply maintain a lazy const and lazy sum of B.

Then for each query asking for maximum in $$$[L, R]$$$ range, if it covers a whole block, ask for the best line for $$$lazy$$$ B plus the $$$lazy$$$ const value. If it just conflicts but not covers a block, we can iterate over the conflicting elements.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    P/S: As lazy B only increases, and the sorting the lines again for each reset is not necessary cause the slopes are const, I think this is doable in $$$O(N$$$ $$$*$$$ $$$sqrt(N$$$$$$))$$$.

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

      So, if $$$B$$$ can be both positive and negative, we may need to maintain the convex hull dynamically?

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

        Not really. Since we do not have to insert or delete a line from the hull, dynamic convex hull (if I do not misunderstand what u said) is not necessary. Instead, you can just implement casual convex hull and binary search for each lazy B instead of using an increasing pointer like when B is positive.

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

          It took me a lot of time, but I finally understand now. Since the lines are fixed, we know the intersection points in the convex hull. So we can find the optimal line with binary search for some $$$x$$$.

          Thanks for your reply.

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

(Sorry. Misread the statement.)

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

You can solve by SQRT-Decomposition. For each block you are able to maintaina convexhull Updating and querying will be solved easy in O(Nsqrt(N))

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

Can you please provide a link to the problem?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

I have tried to code the Solution.

The solution is working for 32-bit numbers. I have made appropriate comments if need be to use it for 64-bit numbers.

As of now I have considered that B can be positive or negative. Thus the time complexity is $$$O(sqrt(N))$$$ per update and $$$O(sqrt(N) * log(N))$$$ per query. Hence making overall complexity $$$O(Q * sqrt(N) * log(N))$$$

If $$$B$$$ is always non-negative than we can reduce the $$$log(N)$$$ factor from query thus it would result in complexity $$$O(sqrt(N))$$$ per query. Thus overall complexity becomes $$$O(Q * sqrt(N))$$$. I have made appropriate comment in the code to change if $$$B$$$ is non-negative (Change the binary search of convex hull trick query to linear one).

I realised lately that my code works on similar idea as suggested by ngfam. Let me know if I am in wrong direction.