题解：P14180 「FAOI-R8」奶龙大战暴暴龙

· · 题解

不算难想难写的细节题。

无解是好判的，就是看看 n,m 是否相等，两个序列是否同构。

先重编号一下，变成两个排列。

特判掉 n=1,n=2,n=3 的特殊情况，手玩一下，列出所有情况就行。

因为最大操作次数为 n，考虑一位一位的去拼。

若当前已经拼好了 1 到 i-1 位，分类讨论 i 的位置。

但是，有一个问题，如果拼好了 1 到 n-2 位，此时 n-1 处在 n 的位置上，不能进行第二种情况的操作。

剩余两次操作机会，考虑把整个序列拼好。

因为 n-2 前面有数了，所以可以看成一个整体操作。

先把 n-2 的整体拼到 n 的后面，然后把 n-2 和 n-1 一起移到 n 的前面就行了。

找位置可以维护一颗平衡树，类似 P3165 的方法找。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<int,int> 
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
namespace cute_fzj_kuai_ruarua{
    int n,m,a[100005],b[100005],c[100005];
    int cnt=0;
    int ls[100005],rs[100005],siz[100005],val[100005],mn[100005],key[100005],root;
    int newnode(int x){
        cnt++;
        siz[cnt]=1;
        ls[cnt]=0;
        rs[cnt]=0;
        val[cnt]=x;
        mn[cnt]=x;
        key[cnt]=rand();
        return cnt;
    }
    void pushup(int x){
        mn[x]=val[x];
        if(ls[x]) mn[x]=min(mn[x],mn[ls[x]]);
        if(rs[x]) mn[x]=min(mn[x],mn[rs[x]]);
        siz[x]=siz[ls[x]]+siz[rs[x]]+1;
    }
    void split(int x,int v,int &l,int &r){
        if(!x){
            l=0;
            r=0;
            return ;
        }
        if(siz[ls[x]]>=v){
            r=x;
            split(ls[x],v,l,ls[x]);
        }else{
            l=x;
            split(rs[x],v-siz[ls[x]]-1,rs[x],r);
        }
        pushup(x);
    }
    int merge(int x,int y){
        if(!x||!y) return x|y;
        if(key[x]>key[y]){
            rs[x]=merge(rs[x],y);
            pushup(x);
            return x;
        }else{
            ls[y]=merge(x,ls[y]);
            pushup(y);
            return y;
        }
    }
    int find(int x){
        if(!x) return 0;
        if(mn[x]==val[x]) return siz[ls[x]]+1;
        if(mn[x]==mn[ls[x]]) return find(ls[x]);
        return siz[ls[x]]+1+find(rs[x]);
    }
    void debug(int x){
        if(!x) return ;
        debug(ls[x]);
        cout<<val[x]<<' ';
        debug(rs[x]);
    }
    ve<pair<pii,int> >ans;
    queue<int>q[100005];
    void solve(){
        cnt=0;
        root=0;
        ans.clear();
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i];
        if(n!=m){
            cout<<-1<<endl;
            return ;
        }
        for(int i=1;i<=100000;i++) c[i]=0;
        for(int i=1;i<=n;i++){
            c[a[i]]++;
            c[b[i]]--;
        }
        for(int i=1;i<=100000;i++){
            if(c[i]!=0){
                cout<<-1<<endl;
                return ;
            }
        }
        if(n==2){
            if(a[1]==b[1]&&a[2]==b[2]) cout<<0<<endl;
            else cout<<-1<<endl;
            return ;
        }
        if(n==3){
            if(a[1]==b[1]&&a[2]==b[2]&&a[3]==b[3]) cout<<0<<endl;
            else{
                if(b[1]==a[3]&&b[2]==a[1]&&b[3]==a[2]){
                    cout<<1<<endl;
                    cout<<1<<" "<<2<<" "<<1<<endl;
                }else if(b[1]==a[2]&&b[2]==a[3]&&b[3]==a[1]){
                    cout<<1<<endl;
                    cout<<2<<' '<<3<<" "<<0<<endl;
                }else cout<<-1<<endl;
            }
            return ;
        }
        for(int i=1;i<=n;i++){
            q[b[i]].push(i);
        }
        for(int i=1;i<=n;i++){
            int _=a[i];
            a[i]=q[a[i]].front();
            q[_].pop();
            root=merge(root,newnode(a[i]));
        }
        for(int i=1;i<=n-2;i++){
            int pos=find(root);
            int len=n-i+1;
//          cout<<pos+i-1<<" "<<len<<endl;
            if(pos==1){
                int x,y;
                split(root,1,x,y);
                root=y;
                continue;
            }
            if(pos==len){
                ans.pb(mk(mk(i,n-1),i));
                int x,y;
                split(root,len-1,x,y);
                root=x;
                continue;
            }
            ans.pb(mk(mk(pos+i-1,n),i-1));
            int x,y;
            split(root,pos-1,x,y);
            root=merge(y,x);
            split(root,1,x,y);
            root=y;
//          for(int j=1;j<=i;j++) cout<<j<<" ";
//          debug(root);
//          cout<<endl;
        }
        int pos=find(root);
        if(pos==2){
            ans.pb(mk(mk(1,n-2),1));
            ans.pb(mk(mk(2,n),0));
        }
        cout<<ans.size()<<endl;
        for(auto y:ans) cout<<y.fi.fi<<' '<<y.fi.se<<' '<<y.se<<endl;
    }
    void main(){
        srand(time(0));
        int T,_;
        cin>>T>>_;
        while(T--) solve();
    }
}
using namespace cute_fzj_kuai_ruarua;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cute_fzj_kuai_ruarua::main();
    return 0;
}