题解：P17196 [KOI 2026 #2] 序列运算

· · 题解

注意到一个简单性质，如果存在 i<j 使得 a_i>a_j，那么 a_i 无论如何都不能跑到 a_j 后面。

另一个性质是，对于最终不在 b 序列中出现的数，在它能被删除时，一定会删除它，因为含有这些数的交换不会改变最终在 b 序列中出现的数的相对位置，即不影响 b 序列中出现的数，而这些数的删除也是互不影响的，因为如果较小的数被删除，它旁边一定会有比它更小的数，原来能被它删除的数也能被这个更小的数删除，所以能删就删不会产生后效性，是正确的。

考虑我们依次将 b_1 到 b_m 的每一个数移动到对应位置，处理 b_i 时，先找到 b_i 在当前 a 中的位置 a_j，如果 a_j>a_{j+1} 则由第一条性质不用考虑它对后面的贡献，如果 a_{j+1} 在 b 中出现，因为我们是依次枚举的，所以 a_{j} 一定在前，同样不用考虑对后面的贡献，如果都不满足由第二条性质把 a_{j+1} 删掉并重复流程即可，接着将 a_j 往前移动，a_{j-1} 如果能删且该删就删，不能删且无法交换那由第一条性质直接输出无解，否则直接交换即可。

考虑实现，因为每个数只会被删除一次所以直接使用 vector.erase 即可，交换是简单的。

::::info[时间复杂度 O(n^2)，点此查看代码]

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
vector<pair<int,int>> ans;
vector<int> a;int n,m,b[N],vis[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m,a.resize(n+2,0);
    for(int i=1;i<=n;i++)  cin>>a[i];
    for(int i=1;i<=m;i++)  cin>>b[i],vis[b[i]]=1;
    for(int i=1;i<=m;i++){
        int j=1;
        while(a[j]!=b[i])  j++;
        while(a[j]<a[j+1]&&!vis[a[j+1]]){
            ans.emplace_back(2,j);
            a.erase(a.begin()+j+1);
        }
        while(1){
            if(i==j)  break;
            while(a[j]<a[j-1]&&!vis[a[j-1]]){
                ans.emplace_back(2,j-1);
                a.erase(a.begin()+j-1),j--;
            }
            if(i==j)  break;
            if(a[j]<a[j-1])  return cout<<"NO\n",0;
            swap(a[j],a[j-1]),ans.emplace_back(1,--j);
        }
    }
    while(a.size()>m+2){
        if(a[m+1]<a[m])  return cout<<"NO\n",0;
        a.erase(a.begin()+m+1),ans.emplace_back(2,m);
    }
    cout<<"YES\n"<<ans.size()<<"\n";
    for(auto [x,y]:ans)  cout<<x<<" "<<y<<"\n";
}

::::