Three Permutations and Queries

For two values $x,y$, orient an edge $x \to y$ if $x$ appears before $y$ in at least two of the three permutations. Exactly one direction is chosen for every pair, so this is a tournament. A good permutation exists exactly when there is a linear order consistent with every edge of this tournament, which is equivalent to the tournament being transitive.

For every value $x$, define

$$d[x]=\#\{y:\text{$y$ appears before $x$ in at least two of the three permutations}\}.$$

Thus, $d[x]$ is the indegree of $x$ in the tournament.

In a transitive tournament, the indegrees are exactly $0,1,\cdots,N-1$. Conversely, if all $d[x]$ are distinct, then because every indegree lies between $0$ and $N-1$, the set of indegrees is exactly . The vertex of indegree is before every other vertex. Removing it leaves a tournament whose indegrees are again , so induction shows that the tournament is transitive. Therefore, a good permutation exists if and only if all values are distinct.

It remains to compute the initial $d[x]$ efficiently. Let $\operatorname{pos}_u[x]$ be the position of $x$ in permutation $u$. For two permutations , define

$$C_{uv}[x]=\#\{y:\operatorname{pos}_u[y]<\operatorname{pos}_u[x],\ \operatorname{pos}_v[y]<\operatorname{pos}_v[x]\},$$

and let $C_{pqr}[x]$ be the number of values that appear before $x$ in all three permutations. If a fixed $y$ appears before $x$ in exactly of the three permutations, it contributes to and contributes once to only when . Hence

$$d[x]=C_{pq}[x]+C_{pr}[x]+C_{qr}[x]-2C_{pqr}[x].$$

Each $C_{uv}$ can be computed in $O(N\log N)$ by scanning one permutation and inserting positions in the other permutation into a Fenwick tree. Computing $C_{pqr}$ is a three-dimensional dominance counting problem on the three positions. Sort by the position in , then use CDQ divide and conquer with a Fenwick tree to obtain all values in .

Now consider a query. Suppose the two adjacent values in the selected permutation are $x,y$, with $x$ before $y$ before the swap. Swapping adjacent elements changes the relative order of only the pair $(x,y)$ in that permutation. Therefore, only the tournament edge between $x$ and can possibly change.

If the other two permutations agree on the order of $x,y$, the majority result is already fixed and nothing changes. If the other two permutations disagree, then the edge is $x\to y$ before the swap and becomes $y\to x$ after the swap. Only in this case, update

$$d[x]\mathrel{+}=1,\qquad d[y]\mathrel{-}=1.$$

Maintain the frequency of each possible indegree $0,1,\cdots,N-1$, together with the number of indegree values whose frequency is at least $2$. This number is $0$ exactly when all $d[x]$ are distinct. At most two indegrees change in one query, so this maintenance takes time. Also maintain the current position arrays of the three permutations, allowing the order comparison in the other two permutations to be done in .

The initialization takes $O(N\log^2 N)$ time, every query takes $O(1)$ time, and the memory usage is $O(N)$. Thus the total time complexity is .

Solution written by GPT5.6