CF2041J题解

· · 题解

好题。

考虑对于一个给定的 b 序列如何 check。有一个 O(n^2) 的 f_{l,r} 表示前 r-l+1 大的 b_i 能否放进 [l,r] 中。但是这明显没有利用完全性质。

将 b 从大往小排序，若存在一个长度 \ge i 的包含 j 的连续段，满足其中的值都大于 b_i，那么我们记 f_{i,j} = 1。最后，若有一个 j 满足其 f_{i,j} 均为 1，那么此 b_i 序列合法，且此时 b_1 填在 j 这个位置。

必要性是显然的，若 i 时刻 j 这个连通块都没有 i 个位置 \ge b_i 显然非法。

充分性同样易证，如果对于每个时刻都有这样的连通块，那么我们显然可以将每次新增加的 b_i 填在最后一个加入该连通块的位置。

此时，我们只需要支持将某个位置设为 1（表示其 \ge b_i），同时对所有长度 \ge i 的连续段，将其中的 f_{i,j} 设为 1。关于连续段的维护是并查集的经典问题，而对于找到所有长度 \ge i 的连续段，我们可以参考优秀的拆分，对总计 n\ln n 个关键点进行询问，若满足条件则对区间赋值做简单差分。此刻将 check 做到 O(n\ln n)。

考虑 b_i -1 的意义，其仅对第 i 大值产生影响。此时我们多出了一些 =b_i 的位置，将这些位置及关于这些位置连通的位置的 f_{i,j} 设为 1 的代价为 1。不妨仿照上述过程，在差分过程中维护 c_{i,0/1} 表示当前位置 j 的 f_{i,j} 设为 1 的代价能否为 0/1，简单讨论即可维护。

时间复杂度：O(n\ln n)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int n,b[N],fa[N],L[N],R[N],c[N][2],sum,ok;
bool vis[N];
struct node{
    int c,v,op;
};
vector<node>v[N];
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
    x=find(x),y=find(y);
    fa[x]=y;L[y]=min(L[y],L[x]);R[y]=max(R[y],R[x]);
}
struct qwq{
    int x,id;
    inline bool operator<(qwq b){
        return x>b.x;
    }
}a[N];
int main(){
    n=read();
    for(int i = 1;i<=n;i++)a[i].x=read(),a[i].id=i;
    sort(a+1,a+n+1);
    for(int i = 1;i<=n;i++)b[i]=read();
    sort(b+1,b+n+1,greater<int>());
    for(int i = 1,lst=1;i<=n;i++){
        while(lst<=n&&a[lst].x>b[i]){
            int x=a[lst].id;
            vis[x]=1;fa[x]=x;L[x]=R[x]=x;
            if(vis[x-1])merge(x,x-1);
            if(vis[x+1])merge(x,x+1);
            lst++;
        }
        for(int j = i;j<=n;j+=i){
            if(!vis[j])continue;
            int x=find(j);
            // cerr<<i<<' '<<j<<' '<<x<<endl;
            if(R[x]-L[x]+1<i)continue;
            v[L[x]].push_back({i,0,1});v[R[x]+1].push_back({i,0,-1});
        }   
        while(lst<=n&&a[lst].x==b[i]){
            int x=a[lst].id;
            vis[x]=1;fa[x]=x;L[x]=R[x]=x;
            if(vis[x-1])merge(x,x-1);
            if(vis[x+1])merge(x,x+1);
            lst++;
        }
        for(int j = i;j<=n;j+=i){
            if(!vis[j])continue;
            int x=find(j);
            if(R[x]-L[x]+1<i)continue;
            v[L[x]].push_back({i,1,1});v[R[x]+1].push_back({i,1,-1});
        }   
    }
    int ans = 1e9;
    for(int i = 1;i<=n;i++){
        for(auto[a,v,op]:v[i]){
            if(op==1){
                c[a][v]++;
                if(c[a][v]==1){
                    if(!c[a][v^1])ok++,sum+=v;
                    else if(v==0)sum--;
                }
            }
            else{
                c[a][v]--;
                if(c[a][v]==0){
                    if(!c[a][v^1])ok--,sum-=v;
                    else if(v==0)sum++;
                }
            }
        }
        if(ok==n)ans=min(ans,sum);
        // cerr<<i<<' '<<ok<<endl;
    }
    if(ans==1e9)printf("-1");
    else printf("%d",ans);
    return 0;
}