Or is this not the correct way at all? Anyway, how to solve F?

So you can calculate this dp by BST (or priority_queue) in $$$O(N\log^2N)$$$ time.

Could you elaborate on this?

The intended solution utilizes the combinatorial structure of the answer much more. Maybe I should work harder to come up with a version before the contest that asks the answer for all $$$k=1\dots n$$$.

Here is a sketch of the intended solution.

The intended solution is centroid decomposition. Find the $$$k$$$-th farthest vertices of centroid. If some subtree contains more than $$$\frac{k}{2}$$$, move to this subtree. And we do the same thing in the subtree. However, it only works for $$$k$$$ is an even number. For the odd case, we can prove the optimal solution is the optimal solution for $$$k-1$$$ with one more vertex.

Time complexity is $$$O(n\log^2 n)$$$. We can improve it to $$$O(n\log n)$$$ using nth_element.

Our solution for E required too much case work, is it possible to avoid it.

In G, using hill climbing we manage to get a solution that satisfied the distance among the points, but was not coplanar enough (the best achieved was 5e-18).

H: Assume at some point we add $$$l$$$ elements to the left and after that $$$r$$$ elements to the right. When is it better to change order and add $$$r$$$ right elements first and after that $$$l$$$ elements to the left? When the average of right elements is less than the average of left elements. So let's think geometrically: draw 2 polylines: the first one will contain vectors $$$(1, a[i])$$$ for all elements to the left of start in order in which they are added and similar for elements to the right. Compute lower convex hull of both polylines. Each edge of convex hull corresponds to a group of points that will always be added together. Now all we need to do is to calculate for each edge of the first convex hull number of edges in the second convex hull which are greater than it and vice versa. When we change starting point, both convex hulls and the answer can be easily maintained with stacks. Code.

B:

For each query of second type add edge between $$$u_p$$$ and $$$v_p$$$ with weight equal to query index. Now answer to query of first type with query index $$$T$$$ is equal to "how many vertices are achievable from vertex $$$u$$$ if we can move only with edges with increasing weights and with weights $$$\le T$$$ (it is good to think about weights as time).

This can be solved using centroid decomposition. Assume we found centroid $$$r$$$. Let's root tree in $$$r$$$. We will calculate for each query in $$$u$$$ only vertices $$$v$$$ such that simple path pass centroid.

For each vertex $$$v$$$ compute $$$travel_v$$$ equal to minimum time required to reach centroid from vertex $$$v$$$ and for each edge from $$$p_v$$$ to $$$v$$$ find maximum time when we can leave centroid and reach vertex $$$v$$$ with this edge.

Now for query in $$$u$$$ with time $$$T$$$ answer is — how many vertices in our tree (except my subtree) has path which starts in centroid after time $$$travel_u$$$ and reaches that vertex before $$$T$$$. It can be done with sweeping technique. Complexity $$$O(N \log ^2 N)$$$.

J: take the smallest integer $$$q$$$ so that $$$2^q \ge |S|$$$ and consider the finite field $$$\mathbb{F}_{2^q}$$$. Now, for each integer $$$i$$$ from $$$0$$$ to $$$|S| - 1$$$, compute $$$i^3$$$ in this field (call the result $$$f(i)$$$) and output $$$i \cdot 2^q + f(i)$$$ (computed normally in $$$\mathbb{Z}$$$).

As $$$f(i) \in \mathbb{F}_{2^q}$$$, then $$$f(i) < 2^q$$$ and therefore $$$i \cdot 2^q + f(i) < |S| \cdot 2^q < |S| \cdot 2|S| = 2|S|^2 \le n$$$.

Now, assume $$$a_{i_1} \oplus a_{j_1} = a_{i_2} \oplus a_{j_2}$$$. It means that $$$i_1 \oplus j_1 = i_2 \oplus j_2$$$ (or, in $$$\mathbb{F}_{2^q}$$$, simply $$$i_1 + j_1 = i_2 + j_2$$$) and $$$i_1^3 - j_1^3 = i_2^3 - j_2^3$$$. As $$$x^3 - y^3 = (x-y)(x^2 + xy + y^2)$$$ (and $$$y = -y$$$ within this field), we have that $$$i_1^2 + i_1j_1 + j_1^2 = i_2^2 + i_2j_2 + j_2^2$$$. Then, $$$(x + y)^2 = x^2 + y^2$$$ within the field, so we also have $$$i_1j_1 = i_2j_2$$$.

Let $$$s := i_1 + j_1$$$, $$$p := i_1j_1$$$. Now, each of the values $$$i_1$$$, $$$j_1$$$, $$$i_2$$$, $$$j_2$$$ satisfies the polynomial equation $$$x(s - x) = p$$$. This polynomial has degree 2, so it has at most 2 solutions in the field. As $$$i_1 \neq j_1$$$, $$$i_2 \neq j_2$$$ and $$${i_1, j_1} \neq {i_2, j_2}$$$, we arrive at contradiction.

It looks there should be a conditional lower bound (like $$$\Omega(\sqrt{n})$$$) about fully 2D lazy update.

The intended solution is D&C and sweep line.

Thanks ko_osaga teacher. Let‘s wait for Yuhao Du contest 11.

I hope this is sarcasm.

http://opentrains.snarknews.info/~ejudge/flg.cgi?sid=fe24381eae9c1260 statements

Tutorial slides: http://acm.math.spbu.ru/trains/191215.slides.en.pdf.
Best viewed one per page, otherwise scrolling will be nonsensical.
Feel free to ask more specific questions if the solutions outlined in the slides are not clear.

jqdai0815 pls help D: