Binary Search with One Swap

Research used: the official Codeforces problem/editorial page for Educational Codeforces Round 187, which contains the reference solution for 2203F, plus the Codeforces status page showing accepted C++ submissions: https://codeforces.com/blog/entry/151612 and https://mirror.codeforces.com/problemset/status/2203/problem/F. The writeup below is original and verified against the supplied statement and samples.

Index everything from $0$ to $n-1$ for the explanation. The array is initially $a_p=p$. Binary search over positions is exactly searching in an implicit BST:

• the root of an interval $[l,r]$ is $m=\lfloor(l+r)/2\rfloor$;
• the left child is built on $[l,m-1]$;
• the right child is built on $[m+1,r]$.

In the sorted array, searching for value $x$ walks from the global root to node $x$.

Now swap two positions $u<v$. Only nodes $u$ and $v$ have wrong values. Everywhere else the comparison is still the normal BST comparison. So the swap only matters when the search path reaches one of these two nodes.

The key classification is by $c=\operatorname{LCA}(u,v)$ in the implicit BST. Every unordered pair has exactly one such LCA, and inside the subtree of $c$, the pair is one of three types:

1. $c$ swapped with a node in its left subtree;
2. $c$ swapped with a node in its right subtree;
3. one endpoint in the left subtree and the other in the right subtree.

This is the whole problem. Trying to simulate every pair is $O(n^2\log n)$, i.e. dead on arrival.

Suppose the current subtree has length $s$ and root position $m=\lfloor(s-1)/2\rfloor$ relative to this subtree.

If we swap the root $m$ with a left node $u<m$, the root stores value $u$. Values $x\le u$ still go left correctly, value $u$ itself is found immediately, and values $u<x\le m$ are sent right or miss equality incorrectly. So exactly

$m-u$

values are lost. Similarly, swapping the root with a right node $v>m$ loses

$v-m$

values.

Now take the split case: $u<m<v$. At node $u$, the stored value is $v$, which is larger than every value in the left side of $m$. Therefore, when searching inside the subtree of $u$, all values that should stop at $u$ or go right from $u$ are destroyed. That count is

$1+\operatorname{rightSize}(u).$

At node $v$, the stored value is $u$, which is smaller than every value in the right side of $m$. Symmetrically, it destroys

$1+\operatorname{leftSize}(v).$

These two sets of lost values are disjoint, so the total loss is

$\operatorname{loss}(u,v)=1+\operatorname{rightSize}(u)+1+\operatorname{leftSize}(v).$

The beauty of the pair is then

$n-\operatorname{loss}(u,v).$

So for each subtree length $s$, we compute a small distribution $g_s[d]$: the number of pairs whose LCA is the root of this subtree and whose swap loses exactly $d$ values. Then if the whole global tree contains $cnt_s$ subtrees of length $s$, we add

$cnt_s\cdot g_s[d]$

to answer bucket $p_{n-d}$.

How do we get $cnt_s$? Just DFS over subtree lengths. A subtree of length $s$ has children

$L=\left\lfloor\frac{s-1}{2}\right\rfloor,\qquad R=s-1-L.$

Increment $cnt_s$, recurse into $L$ and $R$, ignoring zero lengths.

For $g_s$, build an array sub[p] for relative positions $p\in[0,s-1]`, where `sub[p]` is the size of the BST subtree rooted at$p$inside this length-$s$ tree. This is another simple recursive fill.

Then:

• root-left pairs add one pair to loss $m-u$;
• root-right pairs add one pair to loss $v-m$;
• split pairs are counted by grouping possible left losses and right losses:

$leftLoss(u)=1+rightSize(sub[u]),$

$rightLoss(v)=1+leftSize(sub[v]).$

For every possible pair of grouped losses $(a,b)$, add

$countLeft[a]\cdot countRight[b]$

to $g_s[a+b]$.

Why is this fast enough? The implicit binary-search tree has only $O(\log n)$ different subtree sizes per level, and the sum of all distinct sizes we process is $O(n)$. More concretely, the sizes shrink by about half, so the total work over all distinct $s$ with $cnt_s>0$ is linear-ish. The grouping maps have only $O(\log s)$ distinct keys because subtree sizes on one side take only a few values per depth. Constraints are tight, but this is not magic; it is just avoiding the $n^2$ trap.

Edge cases:

• $p_n=0$ for $n\ge3$: every swap loses at least one value.
• Loss values are at most the current subtree length, so final buckets are always valid.
• Use long long; the number of pairs is about $1.25\cdot10^{13}$ when $n=5\cdot10^6$.

Complexity: $O(n)$ total generated subtree-position work, with tiny logarithmic grouping overhead from maps in practice. Memory is $O(n)$ for the answer and count arrays, plus temporary arrays for one processed subtree length.