CF2059E1 题解

huangrenheluogu · 2025-02-04 18:15:45 · 题解

相当于，一个长度为 n\times m 的序列，有 m 个可以插入的位置（m 块），看最小的从 a 到 b 的步骤。

考虑必要条件。考虑如果 a_i 最后不在 b 序列中对应的位置，那么 a_i 必须被弹出，则最后 ans\ge n-i+1，因此，尽量让一个前缀的点可以匹配。记 i 匹配的位置为 mat_i（不存在显然 i 不行）。

• 如果 mat_i-i\lt mat_{i-1}-(i-1)，i 就不可行了。
• 如果 mat_i-i= mat_{i-1}-(i-1)，显然没事。
• 如果 mat_i-i\gt mat_{i-1}-(i-1)，需要中间有点可以分开，就是 mat_i\ge R_{bel_i}，R_{bel_i} 是 i 所在的块的右端点。

考虑 i 不可行之后，需要把 i 弹出去，因此，这个块的点必须右移 stp=R_{bel_i}-i+1 步。考虑左端点和其对应的点，是这个块中距离最小的一对，如果距离不到 stp 步，这个块都不行了；否则，[1,i-1] 就是最长的可行的前缀。

考虑构造方案，(i,i+1) 之间插入的数字是容易处理的。考虑插入的位置是 i 移动到一个块的右端点的时候。当前插入最后一个可以插入的点，这样可以插入的点还是可以插入。考虑维护最后一个可以插入的点，用 set 维护；如何判断后面是否有点可以加入？用线段树维护即可。

因为可以构造方案，说明了上面的步数分析是充要的。

#include<bits/stdc++.h>
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid (l + r >> 1)
using namespace std;
const int N = 3e5 + 5;
int T, n, m, a[N], b[N], bel[N], pos[N << 1], ans;
int f[N];
inline void chkmax(int &x, int y){
    if(x < y) x = y;
}
inline void solve(){
    scanf("%d%d", &n, &m);
    n *= m;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++){
        scanf("%d", &b[i]);
        pos[b[i]] = i;
    }
    for(int i = 1; i <= n; i++) bel[i] = (i - 1) / m + 1;
    bool flg = 0;
    for(int i = 1, p; i <= n; i++){
        if(!pos[a[i]]){
            flg = 1;
        }
        else if(i > 1 && pos[a[i]] - i < pos[a[i - 1]] - (i - 1)){
            flg = 1;
        }
        else if(i > 1 && pos[a[i - 1]] < m * bel[i - 1] && pos[a[i]] - i > pos[a[i - 1]] - (i - 1)){
            flg = 1;
        }
        if(flg){
            p = (bel[i] - 1) * m + 1;
            if(p + (p + m - i) > pos[a[p]]){
                printf("%d\n", n - p + 1);
                return ;
            }
            else{
                printf("%d\n", n - i + 1);
                return ;
            }
        }
    }
    printf("%d\n", 0);
}
inline void clr(){
    for(int i = 1; i <= n * 2; i++){
        pos[i] = 0;
    }
}
int main(){
    // freopen("data.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    scanf("%d", &T);
    while(T--){
        solve();
        clr();
    }
    return 0;
}