kpw29's blog

By kpw29, history, 7 years ago, In English

Hi guys. Today I was solving a problem together with minimario and we came across a well known-looking subproblem we couldn't solve.

There are two sequences of length N, A[] and B[] with N, A[i], B[i] <= 10^5.

Our goal is to answer queries: a, b, x, y which mean : find the i in range <a, b> with the biggest value of A[i] * x + B[i] * y. 1 <= a <= b <= n, -10^5 <= x, y <= 10^5.

Is it possible to do it offline?

Is it possible with operation erase as well? (erase can be seen as setting A[i] = -inf and B[i] = -inf).

Thanks for any suggestions.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

For a = 1 and b = n the task is to find the point (A, B) with maximal projection to the direction (x, y). Now it is very similar to "how many points under the line" queries.

Some discussion about it.

UPD: ok, after yeputons's comment mine is useless

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Note that erase is not equivalent to setting Ai and Bi to  - ∞, because one can then choose negative x and y and get  + ∞ as an answer. On the other hand, if you have removals only and it's offline, you can reverse the order of operations and now you have additions and queries only. And additions can be replaced with "enable" queries.

If we treat Ai and Bi as vectors on the Euclidean plane, each query basically asks us to find a vector Vi among Va, Va + 1, ..., Vb such that V × Vi → max (where V = (a, b)). Let's get rid of range queries for a moment and assume that a = 1 and b = n for all queries. Now we simply have a set of vectors and we want to maximize dot product with an arbitrary vector V. What is dot product? It's basically some kind of "how far in this direction this point lies" measure. Or, in some other sense, it's a directed distance from some line. Anyway, that problem is classical and it can be solved by computing convex hull of Vi and then using some special kind of binary search by angle to find the answer.

That is, if a = 1 and b = n, we can answer queries online in after preprocessing. If we add segment tree here, we get preprocessing (that possibly can be made even after if we merge convex hulls instead of re-building them) and per request.

To support "adding" points we only have to learn how to add a point to a convex hull fast enough, and then we will just add a point to convex hulls. Now that's another classical problem which can be solved using some self-balanced tree (e.g. treap), binary search in that tree and finding tangents to a convex polygon using that binary search and ternary search. I believe that it can be done in in one convex hull, resulting in time per original query.

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

    Thank you for your response guys. It will not be good enough to solve the original problem, but it's always great to have some knowledge. BTW: CEOI 2012 : Circuit

    https://oj.uz/problem/view/CEOI12_circuit

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

      I'm pretty sure that my solution for that CEOI problem does not involve segment tree or any modification queries. I think it's some kind of linear stuff with stack, probably inspired by Graham scan.