https://codeforces.com/gym/101964/problem/F
妈的我往左拓展的部分加了break，往右拓展了地方没加比赛就结束了，而且我当时造的样例已经测出来了这个问题了，艹，少了break;6个字符一题没了
经典拓展问题，就是上面的一个字母对应下面的一段字母，然后这些对应的区间必须是从左往右覆盖完整个区间的，如果出现交叉情况显然是不行的。
所以只要从左到右枚举b中的每个字母，然后用一个a数组的下标指针l 标记b中的每个字母对应哪一个a[l]，然后对应的a[l]必须递增，如果能跑完整个b串，且l<=n，那么就一定有解
接下来我们把需要拓展到b的a中的位置拿出来，ll[i],rr[i]是他们需要拓展的位置，然后我们考虑拓扑序关系，如果出现rr[i]>i+1，那么说明i+1必须在i向右之前把自己要拓展的地方给拓展了，考虑到ll[i],rr[i]是递增且不想交的，所以我们只要dfs就行了
用vis[i]标记某个位置是否被拓展，如果没被拓展过，那么说明他的数字还是原来a数组中的数字，那么需要逐个进行拓展
如果vis[i]已经被拓展过了，那么就能一步到位，因为从这里开始向右(因为拓扑序的原因，向左拓展的情况一定都是逐个拓展的)已经被dfs里面的下一个拓展过了，那么从这里到rr[i]一定都是等于下一个数字，所以直接一步到位，然后对于每个数字的ll[i],rr[i]我们只需要在端点标记vis[i]和吧a[i]赋值过去就行了。
#include<bits/stdc++.h> using namespace std; const int maxl=2e5+10; int n,ans,cnt,sum; int a[maxl],b[maxl],aa[maxl]; int ll[maxl],rr[maxl],du[maxl]; struct opt { int op,l,r; }c[maxl*2]; vector<int> e[maxl]; queue<int> q; bool vis[maxl],ok[maxl]; inline void prework() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); } inline void dfs(int i) { int u=aa[i]; if(rr[u]>=aa[i+1] && i+1<=cnt) dfs(i+1); ok[i]=true; ++sum;int x; if(ll[u]<u) { vis[u]=true; for(int j=u-1;j>=ll[u];j--) if(!vis[j]) { vis[j]=true; x=(int)(a[j]>a[u]); c[++ans]=opt{x,j,j+1}; } else { x=(int)(a[j]>a[u]); c[++ans]=opt{x,ll[u],j+1}; vis[ll[u]]=true;a[ll[u]]=a[u]; break; } } if(rr[u]>u) { vis[u]=true; for(int j=u+1;j<=rr[u];j++) if(!vis[j]) { vis[j]=true; x=(int)(a[j]>a[u]); c[++ans]=opt{x,j-1,j}; } else { x=(int)(a[j]>a[u]); c[++ans]=opt{x,j-1,rr[u]}; vis[rr[u]]=true;a[rr[u]]=a[u]; break; } } } inline void mainwork() { int l=1; for(int i=1;i<=n;i++) { while(b[i]!=a[l] && l<=n) l++; if(l>n) { ans=-1; return; } if(!ll[l]) ll[l]=i; rr[l]=max(rr[l],i); } cnt=0; for(int i=1;i<=n;i++) if(ll[i]) { aa[++cnt]=i; for(int j=ll[i];j<=rr[i];j++) if(ll[j] && j!=i) e[j].push_back(i),du[i]++; } ans=0; for(int i=1;i<=cnt;i++) if(!ok[i]) dfs(i); if(sum!=cnt) { ans=-1; return; } } inline void print() { if(ans<0) puts("-1"); else { printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%c %d %d\n","Mm"[c[i].op==1],c[i].l,c[i].r); } } int main() { prework(); mainwork(); print(); return 0; }
