CF1558F Strange Sort

syzf2222 · 2022-11-04 10:42:13 · 题解

考虑转化为 01 排序，答案即为所有划分值答案的最大值。

容易发现在 01 排序中，相同数字的相对位置不会变化，故答案即为最右侧的 0 的就位时间。

设 f_i 为第 i 个 0 归为的时间，k_i 为其前面 1 的个数，p_i 为其位置。

• 若 p_i=i，则 f_i=0，这显然是一段前缀。

• 否则有 f_i=\max\{f_{i-1}+1,k_i+(p_i\bmod 2)\}。

故 f_i=\max\limits_{j\leqslant i,p_j\neq j}\{ k_j+(p_j\bmod 2)+i-j\}，维护即可。

每一步都很自然，实现也很简单，但为什么我不会呢？

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
int n,m,a[maxn],T,p[maxn],bt[maxn],tr[maxn<<2],laz[maxn<<2];
inline void build(int h,int l,int r){
    tr[h]=-inf;laz[h]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(h<<1,l,mid);
    build(h<<1|1,mid+1,r);
}
inline void pushup(int h,int z){tr[h]+=z;laz[h]+=z;}
inline void pushdown(int h){pushup(h<<1,laz[h]);pushup(h<<1|1,laz[h]);laz[h]=0;}
inline void update(int h,int l,int r,int x,int y){
    if(l==r)return void(tr[h]=y);
    int mid=(l+r)>>1;pushdown(h);
    if(mid>=x)update(h<<1,l,mid,x,y);
    else update(h<<1|1,mid+1,r,x,y);
    tr[h]=max(tr[h<<1],tr[h<<1|1]);
}
inline void modify(int h,int l,int r,int x,int y,int z){
    if(l>y||r<x||x>y)return;
    if(l>=x&&r<=y)return void(pushup(h,z));
    int mid=(l+r)>>1;pushdown(h);
    modify(h<<1,l,mid,x,y,z);
    modify(h<<1|1,mid+1,r,x,y,z);
    tr[h]=max(tr[h<<1],tr[h<<1|1]);
}
inline int query(int h,int l,int r,int x,int y){
    if(l>y||r<x)return -inf;
    if(l>=x&&r<=y)return tr[h];
    int mid=(l+r)>>1;pushdown(h);
    return max(query(h<<1,l,mid,x,y),query(h<<1|1,mid+1,r,x,y));
}
inline void bl(int h,int l,int r){
    if(l==r){
        printf("%d ",tr[h]);
        return;
    }int mid=(l+r)>>1;
    pushdown(h);
    bl(h<<1,l,mid),bl(h<<1|1,mid+1,r);
}
inline void solve(){
    n=read();int ans=0;
    for(int i=1;i<=n;i++)
        a[i]=read(),p[a[i]]=i,bt[i]=0;
    build(1,1,n);
    for(int i=1,pos=1;i<n;i++){
        for(int j=p[i];j<=n;j+=j&(-j))bt[j]++;
        int K=p[i],P=p[i],V=0;
        for(int j=P;j;j-=j&(-j))K-=bt[j];
        while(pos<=n&&a[pos]<=i)++pos;
        if(pos==i+1)continue;
        update(1,1,n,P,K+(P&1)-(P-K));
        modify(1,1,n,P+1,n,-2);
//      printf("i=%d P=%d K=%d res=%d pos=%d\n",i,P,K,i+query(1,1,n,pos,n),pos);
//      bl(1,1,n);puts("");
        ans=max(ans,i+query(1,1,n,pos,n));
    }printf("%d\n",ans);
}
int main(){
    T=read();
    while(T--)solve();
    return 0;
}

深深地感到自己的弱小。