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 walkthrough, 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.
↵
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 walkthrough, 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.
