\[^-^]/

Solved E in $$$O(n \log^2(n))$$$ using binary search over segment tree.

As it's said in editorial, the array of colours is unique and equal to $$$c$$$. This means we can swap only the elements with the same colour. Let's traverse the gravity sort picture columns from right to left. If we collapse the column into contiguous array, the transition from current column to next column looks like inserting an element into array. If the element with colour $$$c_i$$$ is inserted in subarray of colour $$$c_i$$$ with length $$$k$$$, we have $$$k+1$$$ choices for actual position of the element. Then it's enough to maintain the array and find the length of subarray the new element is inserted in.

Let's use the segment trees for min-max (to find the segment with same colour) and sum (to count the elements with same colour). When traversing the elements $$$p_i$$$ in decreasing order, perform the min-max update "assign $$$c_i$$$ to position $$$i$$$" and sum update "increase by $$$1$$$ at position $$$i$$$"; then search the adjacent segments with colour $$$c_i$$$ to the left and to the right of $$$i$$$ with binary search (perform the queries on $$$[m; i]$$$ to the left and $$$[i; m]$$$ to the right) and count the elements on both segments to get $$$k$$$.

On each iteration, the $$$O(\log(n))$$$ queries to segment tree are performed, each query takes $$$O(\log(n))$$$ time, then it's $$$O(\log^2(n))$$$ time per element and $$$O(n\log^2(n))$$$ in total.

Implementation: https://codeforces.me/contest/2064/submission/307630435

For me it's more straightforward then the suggested DSU solution, though the complexity is worse.

I came up with it too

There's a mistake in tutorial for G.

We need to add or subtract 1 on prefix, not suffix. When the pawn mapped to row $$$r$$$ (the minimal row to reach column $$$k$$$) is inserted or deleted, it affects the rows $$$r'$$$ such that $$$r' \leq r$$$ because $$$f(j)$$$ counts pawns no lower than row $$$j$$$. Then we have to update the prefix $$$[1; r]$$$.

The code is correct though.

Another solution for F: For a fixed $$$x$$$, let the $$$(\alpha_1, \alpha_2, \dots, \alpha_s)$$$ be the powers of primes in its factorization. Then, for a fixed $$$|a| = m$$$, the number of arrays is $$$\prod\limits_{i=1}^{s}\binom{m+\alpha_i-1}{\alpha_i}$$$ since we choose positions of primes independently for different primes and for a fixed prime we have a kind of "stars and bars" situation. To get the answer for a certain $$$x$$$, we sum the products for $$$m = \overline{1,n}$$$.

Since $$$n$$$ is large, it's impossible to do explicitly. Instead, notice that $$$\prod\limits_{i=1}^{s}\binom{m+\alpha_i-1}{\alpha_i}$$$ is a polynomial of $$$m$$$ with a degree no more than $$$16$$$ (since there are no more than $$$\log_2{(x)} \leq \log_2{(k)} \lt 17$$$ primes in factorization of $$$x$$$). We can write the polynomial as $$$\sum\limits_{j=0}^{t}c_{xj}\cdot m^j$$$, then the answer for $$$x$$$ is \begin{equation} \sum\limits_{m=1}^{n}\sum\limits_{j=0}^{t}c_{xj}\cdot m^j = \sum\limits_{j=0}^{t}c_{xj}\sum\limits_{m=1}^{n}m^j = \sum\limits_{j=0}^{t}c_{xj}\cdot f_j(n), \end{equation} where $$$f_j(n)$$$ is a sum of first $$$n$$$ $$$j$$$-th powers which is actually a polynomial of degree $$$j+1$$$ (Faulhaber's formula: https://en.wikipedia.org/wiki/Faulhaber%27s_formula ).

We can precompute the coefficients of $$$f_j(x)$$$ for $$$j = \overline{1...\lfloor\log_2(k)\rfloor}$$$ by constructing a system of linear equations and Gaussian elimination in $$$O(\log^4(k))$$$. Then we get an answer for a single $$$x$$$ in $$$O(\log^2(k))$$$ time required for multiplication and evaluation of polynomials.

I found an interesting way to solve E by constructing a different system of linear equations and solving it using a variation of Tridiagonal Matrix Algorithm: https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm.

Let $$$p_v$$$ be the answer for vertex $$$v$$$, $$$p(v)$$$ be the parent of $$$v$$$ and $$$s^*(v)$$$ be the child of $$$v$$$ which lies on the shortest path from $$$v$$$ to leaf in subtree of $$$v$$$. Then we have:

This system is quite difficult to solve in a straightforward way by Gaussian elimination since it requires $$$O(n^3)$$$ time in general, but we can use the approach similar to Tridiagonal Matrix Algorithm in $$$O(n)$$$ time. We express $$$p_{p(v)}$$$ as $$$\alpha_v p_v + \beta_v$$$, substitute this in an equation for $$$p_v$$$ and find coefficients $$$\alpha_{s^*(v)}$$$ and $$$\beta_{s^*(v)}$$$ in terms of $$$\alpha_v$$$ and $$$\beta_v$$$, solve for $$$p_{s^*(v)}$$$ recursively and then solve for $$$p_v$$$.

Then we can implement DFS-like solver which starts from $$$v = 1$$$ with $$$\alpha_1 = 0$$$ and $$$\beta_1 = 1$$$ (since $$$p_1 = 1$$$), propagates $$$\alpha_v$$$ and $$$\beta_v$$$ into $$$s^*(v)$$$, then solves for $$$p_v$$$ and goes into another children. The only problem left is the proper way to "go into another children". Since we've already found $$$p_{p(v)}$$$, from the expression for $$$p_v$$$ we conclude that it's enough to pass $$$\alpha = \frac{1}{2}$$$ and $$$\beta = \frac{1}{2}p_{p(v)}$$$ into DFS call for every child.

Notice that the edutorial's G1 solution is similar to "baby-step giant-step" algorithm for computing the discrete logarithm.

Thank you very much for an explanation for G3! Took a long time to implement solution on my own but this was worthy.

Guessed the answer for C as $$$ans = \max_{i=\overline{0,n-1}}(h_i + i)$$$ (in 0-indexed notation), which is the same as in tutorial if you expand all $$$t_i$$$-s by definition and bring all $$$\max$$$-s outside.

Solved G in a bit different way. First we split array into minimal closed segments staring from the first element, then solve the problem for every segment separately. It's enough to count the number of positions such that, if we light them up, eventually light the first element of segment. Let the segment be $$$(a_0, a_1, ..., a_{2m-1})$$$, then consider colour segments $$$[l_i; \;r_i]$$$ with equal elements on their borders i.e. $$$a_{l_i} = a_{r_i}$$$ $$$(i = \overline{1,m})$$$ and they are sorted in increasing order by $$$l_i$$$. Then position $$$i \in \{0, 1, ..., len-1\}$$$ with corresponding colour segment $$$[l_j; \;r_j]$$$ ($$$i = l_j$$$ or $$$i = r_j$$$) is "good" if and only if $$$i = l_1$$$ OR $$$i = r_1$$$ OR $$$r_1 \in [l_j; \;r_j]$$$ OR $$$[l_j; \;r_j]$$$ contains the "good" position.

We can maintain std::set with indices of "good" positions and std::set with segments between "good" positions. First we insert left and right borders of segments containing $$$r_1$$$. Then for every between-segment $$$[l; \;r]$$$ we check if at least one of colour segments with left border in $$$[l; \;r]$$$ intersects with $$$r+1$$$ (we can do this with segment tree for maximum containing right borders for every left border). If such segment exists, we increment the answer by 2, add its left and right borders in set of "good" positions, recalculate the between-segments, else we just discard the segment because none of its positions can light up the entire closed segment.

It's not the easiest way to solve the problem but it was understandable for me. The implementation much harder than in edutorial: https://codeforces.me/contest/1914/submission/278439465