#14015. Queue Editor 题解

好题多做啊！

首先肯定是要倒着考虑操作序列。（我们认为 $B$ 是较长的队列）

最后添加一个数 $x$，无非就是三种情况：

1. $A$ 添加了， $B$ 没添加这个数，需要 $A$ 的最后一个数是 $x$，$B$ 队列已经有 $x$。我们还原到这个操作之前，要给 $A$ 弹出最后一个数，并给开头补上一个 $A$ 没有的新数。
2. $B$ 添加了， $A$ 没添加这个数，需要 $B$ 的最后一个数是 $x$，$A$ 队列已经有 $x$。我们还原到这个操作之前，要给 $B$ 弹出最后一个数，并给开头补上一个 $B$ 没有的新数。
3. $A$ 和 $B$ 都添加了这个数，需要 $A$ 和 $B$ 的最后一个数是 $x$。我们还原到这个操作之前，要给 $A$ 和 $B$ 弹出最后一个数，并给开头补上各自补上一个没有的新数。

无解情况

我们考虑无解情况。

我们令 $\text{match}$ 代表 $A$ 和 $B$ 共同元素的数量。

那么：

1. $\text{match}=0$：肯定无解，因为最后一步操作都无法还原，不符合上面的任意一种情况。
2. $\text{match}=1$：如果唯一一对相同的数不是两者的最后一个数，一定无解。首先相同的数至少有一个是一个的结尾，要不还是不符合上面的任意一种情况，最后一步操作都无法还原。不妨假设 $A$ 的结尾和 $B$ 中间的某个数相同，因为 $\text{match}=1$，所以剥掉 $A$ 的结尾后，最新的两个队列结尾在另一个队列都没有相同的数，为了能让其做下去，剥掉 $A$ 结尾的数还有在 $A$ 开头的数再补一个 $B$ 结尾的数，这样才能保证有队列的结尾存在对应的数，然后我们就会继续去剥 $B$，这样循环往复下去，我们会发现 $\text{match}$ 永远都等于 $1$，所以无解。
3. $\text{match}>1$：至少存在一个队尾是公共元素。否则一定不合法，理由见上。

我们可以证明其他情况一定能构造出解，理由见下。

朴素情况

我们不妨考虑一种朴素的情况：两个队列的最后一个数相同，其他数均不相同。

我们称两者的公共后缀长度为 $k$，初始 $k=1$。

我们的目标是要做到公共后缀长度为 $m$，这样显然是合法的初始状态。

达成这个目标一共需要三步，我们要保证每一个阶段后两个队列的形式都为前缀的数没有公共元素，长度为 $k$ 的后缀均相同。

第一步 让 $k=1$ 变为 $k=2$

这一步，同时弹掉两者的队尾。需要让 $A$ 插入 $B$ 的队头的第 $2$ 个数，$B$ 插入一个 $A$ 的队尾，这样我们轮流删除 $A$ 队尾，补一个 $B$ 队尾，删除一个 $B$ 队尾，补一个 $A$ 队尾 $\dots$

这本质上就是轮流踢掉两个队列的队尾，直到 $A$ 删除最后一个数 $u$ 后，$A$ 的队尾和 $B$ 的队尾又一样了。这时，我们删完 $u$ 不补 $B$ 的队尾了，补一个 $B$ 队头的第二个数。然后再同时弹掉两者的队尾，$A$ 插入一个 $B$ 的队头， $B$ 插入一个 $A$ 的队尾，这样这两个队列形式为:

a b c d 和 d a b e f。我们再从 $A$ 开始轮流删垃圾队尾，就会把 a b 顶到队尾，于是就从让 $k$ 从 $1$ 变为 $2$。

第二步 让 $k$ 变为 $2k-1$，直到下一步 $k$ 超过 $m$

这一步，我们可以拆为四个阶段来看。

阶段 $A$

拆掉所有公共后缀，将其 $A$ 补上为扣去公共后缀的长度为 $k$ 的 $B$ 的后缀，然后 $B$ 补上 $A$ 的。

以如下两个队列为例：

a b c d e f g A B C D

h i j k l m n o A B C D

我们这一步是要将其变为：

l m n o a b c d e f g

d e f g h i j k l m n o

阶段 $B$

因为当前 $A$ 中长度为 $k$ 的后缀，$B$ 中都有，我们将这段后缀拆掉，继续替换为 $B$ 中的元素，相当于变为如下：

h i j k l m n o a b c

d e f g h i j k l m n o

阶段 $C$

现在 $B$ 有长度为 $2k$ 的后缀 $A$ 中都有，我们可以轮流先做对 $B$ 做操作，插入一个 $A$ 的队尾，然后再对 $A$ 做操作，因为此时 $B$ 队尾可删，我们可以随便插入，我们所有对 $A$ 的操作，都插入 $B$ 当前队头的第二个数（这样操作完 $A$ 和 $B$ 的前缀就相同了）。这个操作我们重复 $2k-1$ 次，因为留一个 $B$ 做下一个阶段的操作，此时两个队列变化如下：

m n o a b c d h i j k

l m n o a b c d e f g h

阶段 $D$

现在我们就剩队尾的垃圾了，我们轮流将 $B$ 的队尾删去，插入 $A$ 的队尾；将 $A$ 的队尾删去，插入 $B$ 的队尾，这样就把两个队列的队尾的垃圾删掉，公共前缀顶到后面来，变为如下：

x f g h m n o a b c d

h i j k l m n o a b c d

这个 $x$ 因为是最后一次，所以不用再插 $B$ 的队头了，随便插一个新元素即可。

至此我们就实现了倍增结尾的公共后缀长度。

第三步 将 $k$ 彻底变为 $m$

如果 $m$ 为偶数：

我们先让 $k$ 先变为 $\frac{m}{2}$，这个只需要一起删 $A$ 和 $B$ 队尾，插入新元素，直到 $k=\frac{m}{2}$。

我们直接套用上一步的阶段 $A $ 和阶段 $B$ 即可， 这样 $A$ 就是 $B$ 的后缀了。

如果 $m$ 为奇数：

我们还是类似做上一步的阶段 $A$ 和阶段 $B$。

我们先让 $k$ 变为 $\frac{m+1}{2}$，方法同上。 假设当前是：

a b A B C

d e f A B C

第一步，同时删除两个队列的队尾，$A$ 补上一个新数，$B$ 补上 $A$ 除了公共后缀外的后缀。

接下来的 $k-1$ 步，同时删除两个队列的队尾，$A$ 补上 $B$ 除了公共后缀外的后缀，$B$ 也补上 $A$ 除了公共后缀外的后缀。

即变为：

e f x a b

x a b d e f

最后我们仿照阶段 $B$，将 $A$ 长度为 $k$ 的后缀分别替换为 $B$ 对应部分即可。

即变为：

a b d e f

x a b d e f

我们就成功了。达到了合法的初始状态。

任意情况

综上，我们我们只要能把任意情况转化到朴素情况，就做完了这道题。

转化成这个朴素情况需要两步：

第一步：让 match 从比 $2$ 大到等于 $2$

这一步的构造就是，删除一个右面的可删元素，判断删完之后是否还是合法情况，如果合法，就在队头插入一个新的数，相当于让 $\text{match}$ 减少 $1$，否则就插入另一个队列结尾的元素，保证操作能一直做下去。这步操作次数是 $O(m)$ 的，因为本质上就是一直轮流把$A$ 和 $B$ 队尾的垃圾删掉，如果遇到 $\text{match}$ 上的元素一定能让 $\text{match}$ 减少，在把两个队列全部扫完之前就一定做完了。

第二步：让 match 从等于 $2$ 到等于 $1$（朴素情况)

和上一步相似的，删除一个最右面的可删元素，判断删完之后是否还是合法情况，如果不是合法情况，我们当然就还需要删完后补上一个另一侧的结尾，这个过程相当于轮流删除 $A$ 和 $B$ 队尾的垃圾。

但是如果删完是合法情况，我们就可以着手构造出朴素情况了。（进行一个大讨论）

1. 假如这一步是删除 $A$ 和 $B$ 的公共队尾，我们根据另一对公共的数（我们称之为 $u$）的位置进行讨论：

   1. 如果另一对仍然是公共队尾，我们直接补一对新的数，就直接变为朴素情况。
   2. 如果 $u$ 在 $B$ 的队尾，却不在 $A$ 的队尾，我们在两个队列队头同时插入一个新数，让它作为朴素情况的公共后缀，因为此时 $u$ 可以删，我们接下来就可以删 $u$ 然后补上 $A$ 的队尾，进行一个从 $B$ 开始轮流删垃圾的过程（$B$ 的垃圾会比 $A$ 多一个），最后就会把我们补的公共后缀顶到结尾。
   3. 如果 $u$ 在 $A$ 的队尾，却不在 $B$ 的队尾：
      1. 如果 $B$ 的队头第二个数（姑且称之为 $x$）不是 $u$，我们可以在 $A$ 插入一个 $x$，$B$ 随便插入一个数，这样我们让 $x$ 作为新的朴素情况的公共后缀，从 $A$ 开始轮流删垃圾，将其顶到队尾（因为 $A$ 的垃圾会比 $B$ 多一个，所以删奇数轮就能达到朴素状态）。
      2. 否则的话，我们令 $B$ 的队头为 $y$，我们可以在 $A$ 插入一个 $y$，和上一种情况一样，唯一区别是 $A$ 和 $B$ 垃圾个数一样多，删偶数轮还是能达到朴素状态。

2. 假如这一步是删除 $A$ 的队尾，我们根据 $u$ 继续讨论：

   1. 如果另一对仍然是公共队尾，我们直接补上新的数，就直接变为朴素情况。
   2. 如果 $u$ 在 $B$ 的队尾：
      1. 如果 $B$ 的队头不是当前删的数，我们直接变为 $B$ 的队头，然后从 $B$ 开始删，最后会把它和 $B$ 的队头顶到队尾（因为$B$ 的垃圾多一个）。
      2. 否则就插入 $B$ 的队头第二个数。这样两者垃圾一样多，还是能到朴素状态。
   3. 如果 $u$ 在 $A$ 的队尾（我们称 $B$ 的队头第二个数、第三个数、第四个数分别为$x$，$y$，$z$）：
      1. 如果 $x$ 不是这一步当前删的数也不是 $u$，我们插入 $x$，然后从 $A$ 开始删垃圾，因为垃圾一样多，所以能一起顶到队尾。
      2. 否则如果 $y$ 不是这一步当前删的数也不是 $u$，我们插入 $y$，然后从 $A$ 开始删垃圾，因为 $A$ 垃圾多一个，所以能一起顶到队尾。
      3. 否则的话一定为 $x$ 和 $y$ 分别为 $u$ 和当前删的牌。我们直接补一个 $z$ 即可，这样我们从 $A$ 开始删垃圾的过程中，$B$ 会因为 $z$ 多删一轮，这个时候情况转为了 3.2（这种情况见后面分析）。

3. 假如这一步是删除 $B$ 的队尾，我们根据 $u$ 继续讨论：

   1. 如果另一对仍然是公共队尾，我们直接补上新的数，就直接变为朴素情况。
   2. 如果 $u$ 是 $B$ 的队尾，因为 $A$ 的队尾一定既不是 $u$ 否则就是 3.1 情况，也不是当前删的数否则就是 1 这个情况大类，我们可以添加一个 $A$ 的队尾，当前 $A$ 的队尾可删，$B$ 的队尾也可删，我们先删 $A$，问题转化为 2.2。
   3. 如果 $u$ 是 $A$ 的队尾，不会出现（我们优先级是先判断 $A$ 是否可删，再判断 $B$ 是否可删，这种情况会落到 2 大类）。

根据上述流程，不难得知这部分最多次数是 $2m$。

至此，我们证明了，对于任意合法情况都可以转化为朴素情况。

综上这道 QOJ 难度 9 的神仙题，也就做完了。

不理解的地方可以参考下面的代码：

#include<bits/stdc++.h>
#define rv std::views::reverse
#define in :
using namespace std;
using std::ranges::iota_view;
auto range(int end){return iota_view((int)1,end+1);}
auto range(int start,int end){if(start>end)return range(0);return iota_view(start,end+1);}
set<int> sA,sB;
set<int> non,gt;
deque<int> A,B;
vector<int> ans;
void addA(int u){
    int x=A.back();
    ans.push_back(x);
    if(gt.count(x)){
        gt.erase(x);
    }else{
        non.insert(x);
    }
    A.pop_back();
    A.push_front(u);
    if(sB.count(u)){
        gt.insert(u);
    }else{
        non.erase(u);
    }
    sA.insert(u);
    sA.erase(x);
}
void addB(int u){
    int x=B.back();
    ans.push_back(x);
    if(gt.count(x)){
        gt.erase(x);
    }else{
        non.insert(x);
    }
    B.pop_back();
    B.push_front(u);
    if(sA.count(u)){
        gt.insert(u);
    }else{
        non.erase(u);
    }
    sB.insert(u);
    sB.erase(x);    
}
int pdc(){
    if(A.back()==B.back()) return 1;
    if(gt.count(A.back())) return 2;
    if(gt.count(B.back())) return 3;
    return 0;
}
int gnew(){
    return *non.begin();
}
int gpair(int u){
    for(auto it=gt.begin();it!=gt.end();it++){
        if((*it)!=u) return *it;
    }
    return 0;
}
void out(){
    for(auto i:A) cout<<i<<" ";
    cout<<"\n";
    for(auto i:B) cout<<i<<" ";
    cout<<"\n-------------------------\n"; 
}
void solve(){
    int m;
    cin>>m;
    sA.clear();
    sB.clear();
    non.clear();
    gt.clear();
    A.clear();
    B.clear();
    ans.clear();
    for(int i=1;i<=2*m+2;i++){
        non.insert(i);
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        A.push_back(x);
        sA.insert(x);
        non.erase(x);
    }
    for(int i=1;i<=m+1;i++){
        int x;
        cin>>x;
        B.push_back(x);
        sB.insert(x);
        if(sA.count(x)) gt.insert(x);
        non.erase(x);
    }
    if(gt.size()==0){
        cout<<"No\n";
        return;
    }else if(gt.size()==1){
        if(A.back()!=B.back()){
            cout<<"No\n";
            return;
        }
    }else{
        if(!pdc()){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
    //match x->2
    while(gt.size()>2){
        int t=pdc();
        if(t==1){
            int ba=A.back();
            int bb=B.back();
            A.pop_back();B.pop_back();
            if(pdc()){
                A.push_back(ba),B.push_back(bb);
                addA(gnew());
                addB(gnew());
            }else{
                int v=B.back();
                A.push_back(ba),B.push_back(bb);
                addA(v);
                addB(gnew());            
            }
            ans.pop_back();
        }else if(t==2){
            int ba=A.back();
            A.pop_back();
            if(pdc()){
                A.push_back(ba);
                addA(gnew());
            }else{
                int v=B.back();
                A.push_back(ba);
                addA(v);
            }            
        }else{
            int bb=B.back();
            B.pop_back();
            if(pdc()){
                B.push_back(bb);
                addB(gnew());
            }else{
                int v=A.back();
                B.push_back(bb);
                addB(v);
            }            
        }
    }
    //match 2->1
    while(gt.size()!=1){
        int t=pdc();
        if(t==1){
            int ba=A.back();
            int bb=B.back();
            A.pop_back();B.pop_back();
            int k=pdc();
            if(k==1){
                A.push_back(ba),B.push_back(bb);
                addA(gnew());
                addB(gnew());
            }else if(k==2){
                A.push_back(ba),B.push_back(bb);
                if(B.front()!=A[m-2]){
                    addA(B.front());
                    addB(gnew());
                }else{
                    addA(B[1]);
                    addB(gnew());
                }
            }else if(k==3){
                A.push_back(ba),B.push_back(bb);
                int x=gnew();
                addA(x);
                addB(x);
            }else{
                int x=B.back();
                A.push_back(ba),B.push_back(bb);
                addA(x);
                addB(gnew());
            }
            ans.pop_back();
        }else if(t==2){
            int ba=A.back();
            A.pop_back();
            int k=pdc();
            if(k==1){
                A.push_back(ba);
                addA(gnew());
            }else if(k==2){
                if(sA.count(B.back())) goto lable;
                if(A.back()==B[m-1]){
                    A.push_back(ba);
                    addA(B.back());
                    addB(gnew());
                    break;
                }
                A.push_back(ba);
                int v=gpair(ba);
                int x=B[1],y=B[2],z=B[3];
                if(x!=ba&&x!=v) addA(x);
                else if(y!=ba&&y!=v) addA(y);
                else addA(z);
            }else if(k==3){
lable:                
                A.push_back(ba);
                if(B[m-1]==ba){
                    addB(gnew());
                    break;
                }                
                if(B.front()!=ba){
                    addA(B.front());
                }else{
                    addA(B[1]);
                }
            }else{
                A.push_back(ba);
                addA(B.back());
            }
        }else{
            int bb=B.back();
            B.pop_back();
            int k=pdc();
            if(k==1){
                B.push_back(bb);
                addB(gnew());
            }else{
                B.push_back(bb);
                addB(A.back());
            }
        }
    }
    // k from 1 to 2
    addA(B[1]);
    addB(A.back());
    ans.pop_back();
    for(int i=1;i<=m-2;i++){
        addA(B.back());
        addB(A.back());
    }
    addA(B[1]);
    addA(B[0]);
    addB(A.back());
    ans.pop_back();
    for(int i=1;i<=m-3;i++){
        addA(B.back());
        addB(A.back());
    }
    addA(B.back());
    addB(gnew());
    // from k to 2k-1
    int k=2;
    while(2*k<m){
        //prod A
        for(int i=1;i<=k;i++){
            addA(B[m-k]);
            addB(A[m-k]);
            ans.pop_back();
        }
        // prod B
        for(int i=1;i<=k;i++){
            addA(B[m-k-i+1]);
        }
        // prod C
        k=2*k-1;
        for(int i=1;i<=k;i++){
            addB(A.back());
            addA(B[1]);
        }
        for(int i=1;i<m-k;i++){
            addB(A.back());
            addA(B.back());
        }
        addB(A.back());
        addA(gnew());
    }
    while(k>((m+1)/2)){
        addA(gnew());
        addB(gnew());
        ans.pop_back();
        k--;
    }
    if(m%2==0){
        for(int i=1;i<=k;i++){
            addA(B[m-k]);
            addB(A[m-k]);
            ans.pop_back();
        }
        for(int i=1;i<=k;i++){
            addA(B[m-k-i+1]);
        }
    }else{
        addA(gnew());
        addB(A[m-k]);
        ans.pop_back();
        for(int i=1;i<=k-1;i++){
            addA(B[m-k+1]);
            addB(A[m-k]);
            ans.pop_back();
        }
        for(int i=1;i<=k;i++){
            addA(B[k-i+1]);
        }
    }
    for(int i=m;i>=0;i--){
        ans.push_back(B[i]);
    }
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto i:ans) cout<<i<<" ";
    cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
}
/*
1
4
1 2 3 4
1 4 5 3 2
*/