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 $\{0,1,\cdots,N-1\}$. The vertex of indegree $0$ is before every other vertex. Removing it leaves a tournament whose indegrees are again $0,1,\cdots,N-2$, so induction shows that the tournament is transitive. Therefore, a good permutation exists if and only if all values $d[x]$ 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 $u,v$, 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 $k$ of the three permutations, it contributes $\binom{k}{2}$ to $C_{pq}+C_{pr}+C_{qr}$ and contributes once to $C_{pqr}$ only when $k=3$. 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 $p$, then use CDQ divide and conquer with a Fenwick tree to obtain all values in $O(N\log^2 N)$.

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 $y$ 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 $O(1)$ time. Also maintain the current position arrays of the three permutations, allowing the order comparison in the other two permutations to be done in $O(1)$.

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 $O(N\log^2 N+M)$.

Solution written by GPT5.6