Heapify 1

Research note: the Codeforces statement is canonical. The official round editorial currently shows code for 2195B instead of a full written explanation; that code repeatedly swaps along chains $i,2i,4i,\ldots$ and then checks whether the array became sorted. Arpa's video-tutorial post links an accepted submission for this problem, and a public solution pattern checks whether position and value differ by a power-of-two factor, which is the same as checking equal odd parts.

Build a graph whose vertices are positions $1,2,\ldots,n$. For every valid operation, there is an edge between $i$ and $2i$. Swapping along an edge means a value can move across that edge. Since we can repeat operations, a value can move anywhere inside its connected component.

Now inspect the shape of this graph. Every position $x$ is connected to $2x$, $4x$, and so on while those positions exist. It is also connected upward to $x/2$ when $x$ is even. Therefore, if you keep dividing a position by $2$ until it becomes odd, that final odd number identifies its whole component.

Define

$$\operatorname{odd}(x)=\frac{x}{2^k}\quad\text{where }2^k\text{ is the largest power of }2\text{ dividing }x.$$

Two positions $u$ and $v$ are in the same connected component exactly when

$$\operatorname{odd}(u)=\operatorname{odd}(v).$$

For example, the component with odd root $3$ is

$$3,6,12,24,\ldots$$

up to $n$.

The target sorted array is fixed: value $x$ must end at position $x$. Since values can never leave their connected component, value $a_i$ currently sitting at position $i$ can reach its final position $a_i$ only if positions $i$ and $a_i$ are in the same component. So a necessary condition is

$$\operatorname{odd}(i)=\operatorname{odd}(a_i)$$

for every $i$.

This condition is also sufficient. If every value belongs to the same component as its target position, then inside each component the set of current values is exactly the same as the set of positions in that component. A connected graph lets us realize any permutation inside the component using swaps along paths. In this problem the components are just chains, so this is even more direct: adjacent swaps along a chain can bubble any value to any place in that chain. No heap magic, just graph components wearing a fake mustache.

So the algorithm is simple:

1. For each index $i$, compute the odd part of $i$.
2. Compute the odd part of $a_i$.
3. If they differ for any $i$, print NO.
4. Otherwise, print YES.

Edge cases:

• $n=1$: already sorted, and the check passes.
• Singleton components, like an odd position $p$ with $2p>n$, cannot exchange values with anything else.
• The array is guaranteed to be a permutation, so we do not need duplicate or range validation.

Complexity: computing an odd part by repeated division takes $O(\log n)$, so the simple implementation is $O(n\log n)$ per test case. Since $\sum n\le 2\cdot10^5$, that is easily fine. Memory usage is $O(1)$ besides input storage, and we can process the values as they are read.