Kth maximum from a set of linear functions.

Revision ru1, by induk_v_tsiane, 2023-09-07 13:15:11

Hi, Codeforces.

Recently I have been thinking about the following task:

You are given $$$N$$$ lines of form $$$f_i(x) = a_i * x + b_i$$$ and $$$Q$$$ queries of form $$$x_j, k_j$$$ — if we sort all of the values of lines in point $$$x_j$$$, which line would be on the $$$k_j$$$-th spot? The queries are offline. I will use $$$K$$$ — the maximum out of all $$$k_j$$$.

I thought about this and developed some methods:

The first one runs in $$$O(sqrt(N)logN + KlogKsqrt(N)$$$ pre query and is online. We use sqrt-decomposition, build CHT on every block, for each query we do the following: run over the blocks, get $$$K$$$ minimums and the blocks where they occurred. Now we know that the needed minimum lies inside one of this blocks, we can now iterate over $$$K * sqrt(N)$$$ blocks, maintaining the $$$K$$$ smallest values with a set.

The second one runs in $$$O(NKlogNlogMAX)$$$ total: for each position from $$$i$$$ to $$$K$$$, we do the following: process the queries left to right, get the current minimum with its index. On the next walkthorugh, we will use D&C to delete that line before this query using Li-Chao tree, and then add it back.

The third one runs in $$$O(N^2logN + QlogQ)$$$. We generate all $$$O(N^2)$$$ points of intersection, sort them together with the requests, then simply swap the two lines which intersect.

So, all of these are kinda not good enough(((. If anyone can share any ideas, I will be extremely grateful.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English induk_v_tsiane 2023-09-07 13:36:33 1449 Initial revision for English translation
ru2 Russian induk_v_tsiane 2023-09-07 13:15:41 2 Мелкая правка: 'ext walkthorugh, we wi' -> 'ext walkthrough, we wi'
ru1 Russian induk_v_tsiane 2023-09-07 13:15:11 1449 Первая редакция (опубликовано)