题解 P5868 【[SEERC2018]Min Max Convert】

· · 题解

[SEERC2018]F-Min Max Convert 题解

\text{Description}

给定两个长度为 n 的序列 A,B。

你有两种操作：

现在你需要构造一个操作方案，在操作次数不超过 2n 的前提下，将 A 变为 B。

##### $\text{Solution}

首先我们将 B 分为若干个区间，同一个区间内所有数相同，相邻区间的数不相同，显然我们要为每个区间在 A 中找到一个对应的数，表示这个区间由该数变换而来，所以两者相等。

接下来有一个结论：

设有区间 I_1:[l_1,r_1],I_2:[l_2,r_2] 满足 r_1\le l_2，那么 I_1 对应的数的位置一定在 I_2 对应的数的位置的左边。

感性理解一下，就是一个数要想跨到另外一个位置，就势必要让中间的信息消失，一条羊肠小道，容不得两虎迎面而过。

所以我们想到一个贪心的方法，设立一个指针 p，然后按顺序枚举 B 里的数，可以匹配的话，就让这个数的对应的数的位置为 p，否则 p 自增 1，如是循环，直至匹配成功。在这个过程中若匹配不了就说明无解。这个过程得复杂度为 O(n)。

现在我们得到了区间与数的对应关系。我们按照区间位置与对应的数的位置的相对关系将区间分为三类：

很显然的是，与前两种区间相关的操作一定要放在与最后一种区间相关的区间前面。

根据上面的结论，我们可以得到一个推论：

与不同种区间相关的操作互不影响；与同种区间相关的操作可能会有影响；与同为第三种区间相关的操作互不影响。

举几个例子就可以理解。

比如说：

3 3 1 3 3 2
1 1 2 2 2 4

我们发现最左边的那个区间和中间那个区间是同是第二种区间，但是会影响到。仔细观察，发现在这种情况下我们让第二种区间从左至右操作即可。

再比如说：

4 1 3 2 3 3 3
4 4 1 1 2 2 2

我们发现中间的那个区间和最右边的那个区间同是第一种区间，但是会影响到。仔细观察，发现在这种情况下我们让第一种区间从右至左操作即可。

综上所述，我们列三个循环，第一个循环，从右至左挖出第一种区间进行操作；第二个循环，从左至右挖出第二种区间进行操作；第三个循环，挖出第三种区间进行操作。

还有一个历史遗留问题，怎么操作？

假定我们正在处理的是区间 [l,r]，对应的数的位置为 p。

首先我们明确一点，若 p 不在区间内，我们要把区间拓宽到包含 p 的大小。

其次我们再明确一定，我们只需要构造出数量在接受条件内的方案就可以了。

若 p 是区间边界，则进行比较，若：

  1. 该位置的数比它旁边的数要大，那么说明这个区间内的最小值不是 p，我们对去除了 p 位置之后剩下的区间做一遍最小值操作，然后对整个区间做一遍最大值操作。
  2. 该位置的数比它旁边的数要小，那么说明这个区间内的最大值不是 p，我们对去除了 p 位置之后剩下的区间做一遍最大值操作，然后对整个区间做一遍最小值操作。

若 p 不是区间边界，则分成两个子区间 [l,p],[p,r] 进行操作。

若某一次操作的区间 [l,r] 满足 l=r，那么可以不做这个操作。

现在证明一下这样子构造的方案是可接受的。

首先，对于 p 是区间边界的区间，最多只要 2 次，否则最多只要 4 次，而这种情况时区间长度一定大于 1。所以这样的话操作次数一定不超过 2n。

具体实现细节可以看代码。

\text{Code}
#include<bits/stdc++.h>
#define REG register
#define MAXN 100005
using namespace std;
inline void read(int& x){
    static char c;
    while(!isdigit(c=getchar()));x=c^48;
    while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

int n;
int A[MAXN],B[MAXN];

char Opt[MAXN<<1];
int OptL[MAXN<<1],OptR[MAXN<<1];
int OptSiz;

int IntL[MAXN],IntR[MAXN],Map[MAXN];
int IntSiz;

inline void Push(char opt,int l,int r){
    if(l==r) return;
    ++OptSiz,Opt[OptSiz]=opt,OptL[OptSiz]=l,OptR[OptSiz]=r;
}

inline void Convert(int l,int r,int pos){
    if(l==r) return;
    if(pos==l)
        if(A[l]<A[l+1]) Push('M',l+1,r),Push('m',l,r);
        else Push('m',l+1,r),Push('M',l,r);
    if(pos==r)
        if(A[r-1]<A[r]) Push('m',l,r-1),Push('M',l,r);
        else Push('M',l,r-1),Push('m',l,r);
    if(pos^l&&pos^r) Convert(l,pos,pos),Convert(pos,r,pos);
}

inline void Work(){
    read(n);
    for(REG int i=1;i<=n;++i) read(A[i]);
    for(REG int i=1;i<=n;++i) read(B[i]);
    for(REG int i=1;i<=n;++i){
        Map[i]=Map[i-1];
        while(Map[i]<=n&&A[Map[i]]^B[i]) ++Map[i];
        if(Map[i]>n){puts("-1");return;}
        if(Map[i]^Map[i-1]) ++IntSiz,IntL[IntSiz]=IntR[IntSiz]=i;
        else ++IntR[IntSiz];
    }
    for(REG int i=1;i<=IntSiz;++i){
        int Mapp=Map[IntL[i]];
        if(Mapp>IntR[i]) Convert(IntL[i],Mapp,Mapp);
    }
    for(REG int i=IntSiz;i;--i){
        int Mapp=Map[IntL[i]];
        if(Mapp<IntL[i]) Convert(Mapp,IntR[i],Mapp);
    }
    for(REG int i=1;i<=IntSiz;++i){
        int Mapp=Map[IntL[i]];
        if(Mapp>=IntL[i]&&Mapp<=IntR[i]) Convert(IntL[i],IntR[i],Mapp);
    }
    printf("%d\n",OptSiz);
    for(REG int i=1;i<=OptSiz;++i)
        printf("%c %d %d\n",Opt[i],OptL[i],OptR[i]);
}

int main(){Work();}