P13509 [OOI 2024] Almost Certainly 题解

Coffee_zzz · 2025-10-05 09:51:05 · 题解

考虑维护一棵值域线段树 T。对于每一个 i，将 T 上 [b_i+1,a_i] 的位置的值加 1，于是 a 可以变成 b 当且仅当 T 上每一个位置都大于等于 0，此时需要的操作次数为 \sum\limits_{i=1}^m a_i-\sum\limits_{i=1}^m b_i。

由于「几乎等价」等价于「各删除一个数后完全相等」，设我们删除的是 a_x 和 b_y，那么我们希望删除的 b_x-a_y 尽可能大，这样才能使操作次数尽可能小。但是我们要保证删除后 T 上每一个位置都大于等于 0，所以需要满足 T 上 [a_y,b_x] 的每一个位置都大于等于 1，于是在 T 上计算最长的大于等于 1 的区间的长度即可。

可以离散化一下，时间复杂度 \mathcal O(n \log n)。

#define int long long
const int N=2e5+5,inf=2e9;
int n,m,ans,a[N],b[N],t[N<<1],val[N<<3],lef[N<<3],rig[N<<3],mid[N<<3],sum[N<<3];
bool tag[N<<3];
void upd(int g){
    sum[g]=sum[g<<1]+sum[g<<1|1];
    lef[g]=max(lef[g<<1],val[g<<1]+lef[g<<1|1]);
    lef[g]=max(lef[g],val[g<<1]);
    rig[g]=max(rig[g<<1|1],rig[g<<1]+val[g<<1|1]);
    rig[g]=max(rig[g],val[g<<1|1]);
    mid[g]=max(mid[g<<1],mid[g<<1|1]);
    mid[g]=max(mid[g],rig[g<<1]+lef[g<<1|1]);
    mid[g]=max(mid[g],max(lef[g<<1|1],rig[g<<1]));
    val[g]=val[g<<1]+val[g<<1|1];
}
void down(int g){
    if(tag[g]){
        tag[g<<1]=tag[g<<1|1]=1;
        tag[g]=0;
        mid[g<<1]=lef[g<<1]=rig[g<<1]=val[g<<1]=sum[g<<1];
        mid[g<<1|1]=lef[g<<1|1]=rig[g<<1|1]=val[g<<1|1]=sum[g<<1|1];
    }
}
void build(int g,int l,int r){
    tag[g]=0;
    if(l==r){
        sum[g]=t[r]-t[r-1];
        mid[g]=0;
        lef[g]=rig[g]=val[g]=-inf;
        return;
    }
    int m=(l+r)>>1;
    build(g<<1,l,m);
    build(g<<1|1,m+1,r);
    upd(g);
}
void modify(int g,int l,int r,int x,int y){
    if(x<=l&&r<=y) return mid[g]=lef[g]=rig[g]=val[g]=sum[g],tag[g]=1,void();
    if(r<x||y<l) return;
    int m=(l+r)>>1;
    down(g);
    modify(g<<1,l,m,x,y);
    modify(g<<1|1,m+1,r,x,y);
    upd(g);
}
void solve(){
    cin>>n,ans=0;
    for(int i=1;i<=n;i++) cin>>a[i],t[i]=a[i];
    for(int i=1;i<=n;i++) cin>>b[i],t[i+n]=b[i];
    sort(t+1,t+n+n+1);
    m=unique(t+1,t+n+n+1)-t-1;
    build(1,1,m);
    for(int i=1;i<=n;i++){
        ans+=a[i]-b[i];
        int x=lb(t+1,t+m+1,b[i])-t,y=lb(t+1,t+m+1,a[i])-t;
        modify(1,1,m,x+1,y);
        cout<<ans-max(mid[1],max(lef[1],max(rig[1],val[1])))<<' ';
    }
    cout<<endl;
}