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.