专栏文章

CF2041J题解

居居然有个高手
CF2041J题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqswvqx
此快照首次捕获于
2025/12/04 10:12
3 个月前
此快照最后确认于
2025/12/04 10:12
3 个月前
查看原文
好题。
考虑对于一个给定的 bb 序列如何 check。有一个 O(n2)O(n^2) 的 fl,rf_{l,r} 表示前 r−l+1r-l+1 大的 bib_i 能否放进 [l,r][l,r] 中。但是这明显没有利用完全性质。
将 bb 从大往小排序，若存在一个长度 ≥i\ge i 的包含 jj 的连续段，满足其中的值都大于 bib_i，那么我们记 fi,j=1f_{i,j} = 1。最后，若有一个 jj 满足其 fi,jf_{i,j} 均为 11，那么此 bib_i 序列合法，且此时 b1b_1 填在 jj 这个位置。
必要性是显然的，若 ii 时刻 jj 这个连通块都没有 ii 个位置 ≥bi\ge b_i 显然非法。
充分性同样易证，如果对于每个时刻都有这样的连通块，那么我们显然可以将每次新增加的 bib_i 填在最后一个加入该连通块的位置。
此时，我们只需要支持将某个位置设为 11（表示其 ≥bi\ge b_i），同时对所有长度 ≥i\ge i 的连续段，将其中的 fi,jf_{i,j} 设为 11。关于连续段的维护是并查集的经典问题，而对于找到所有长度 ≥i\ge i 的连续段，我们可以参考优秀的拆分，对总计 nln⁡nn\ln n 个关键点进行询问，若满足条件则对区间赋值做简单差分。此刻将 check 做到 O(nln⁡n)O(n\ln n)。
考虑 bi−1b_i -1 的意义，其仅对第 ii 大值产生影响。此时我们多出了一些 =bi=b_i 的位置，将这些位置及关于这些位置连通的位置的 fi,jf_{i,j} 设为 11 的代价为 11。不妨仿照上述过程，在差分过程中维护 ci,0/1c_{i,0/1} 表示当前位置 jj 的 fi,jf_{i,j} 设为 11 的代价能否为 0/10/1，简单讨论即可维护。
时间复杂度：O(nln⁡n)O(n\ln n)。
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...