Hello, Codeforces! new round dropping soon btw

There are ways to modify Li Chao Tree to support more powerful types of operations, some of which are already described here. This tutorial will focus on extending the aforementioned data structure to solve the following problem:

• Operation 1: Add a new line
• Operation 2: For a given point, find the line that yields the $$$k$$$-th minimum value at that point

We will assume, without loss of generality, that $$$k$$$ does not change during the queries. Our goal is to perform those operations in $$$O(k \cdot log C)$$$ each. Note that a simple Li Chao Tree solves our problem for $$$k=1$$$.

The Idea

Since a normal Li Chao Tree stores the best line in each node, it is natural to think that all we need to do is to keep the best $$$k$$$ lines. ( where the best line is defined as the line that gives the minimum value when evaluated at the midpoint of the segment ).

This insight, however, proves to be only halfway right, because when popping the worst line from the set we can't really tell where to push it next because it might be useful in both halves. The fix is surprisingly simple: keep $$$2 \cdot k - 1$$$ lines instead.

Why does this work?

It turns out that the worst line will always be above any of the other $$$2 \cdot k - 1$$$ lines in either half.

Suppose it will be above $$$a$$$ lines in the first half and $$$b$$$ in the second. By the claim above, it follows that $$$a + b = 2 \cdot k - 1$$$. Thus, $$$max(a,b) \ge \lceil \frac{2 \cdot k - 1}{2} \rceil = k$$$. This essentially means that in one of the halves it can't be among the $$$k$$$ best lines since there are already $$$k$$$ lines better than it. Now, we can traverse only $$$O(logC)$$$ nodes every update.

Implementation

The overall code slightly differs from the one of a normal Li Chao Tree. To avoid an extra log factor, one could use partial sorting methods, such as nth_element in C++, which works linearly on average.

struct line
{
    int a, b;
    int eval(int x)
    {
        return a * x + b;
    }
};

struct lichao
{
    int n;
    int k;
    vector<vector<line>> a;
    lichao(int n, int k) : n(n), k(k)
    {
        a.resize(4 * n);
    };
    void add_line(int node, int left, int right, line x)
    {
        if (a[node].size() < 2 * k - 1)
        {
            a[node].push_back(x);
            return;
        }
        int mid = (left + right) / 2;

        a[node].push_back(x);

        nth_element(a[node].begin(), a[node].begin() + 2 * k - 2, a[node].end(), [&](line a, line b)
                    { return a.eval(mid) < b.eval(mid); });

        line qui = a[node].back();

        a[node].pop_back();

        if (left == right)
        {
            return;
        }

        int cntl = 0, cntr = 0;
        for (auto i : a[node])
        {
            bool L = qui.eval(left) < i.eval(left);
            cntl += L, cntr += !L;
        }

        if (cntl >= cntr)
        {
            add_line(2 * node, left, mid, qui);
        }
        else
        {
            add_line(2 * node + 1, mid + 1, right, qui);
        }
    }

    void get_candidates(int node, int left, int right, int val, vector<int> &rep)
    {
        for (auto i : a[node])
        {
            rep.push_back(i.eval(val));
        }
        if (left == right)
        {
            return;
        }
        int mid = (left + right) / 2;
        if (val <= mid)
        {
            get_candidates(2 * node, left, mid, val, rep);
        }
        else
        {
            get_candidates(2 * node + 1, mid + 1, right, val, rep);
        }
    }

    int query(int val)
    {
        vector<int> rep;
        get_candidates(1, 1, n, val, rep);
        nth_element(rep.begin(), rep.begin() + k - 1, rep.end());
        return rep[k - 1];
    }
};

Last but not least, thanks to AlexLuchianov for helping development of this trick.

UPD: here is another discussion about this problem.