Solution P14062 | Well I'm still NOOB

· · 题解

注意到进行 k 级排序的时候，已经进行了 2k,3k,4k,\cdots 级排序。

所以取出下标模 k 余 x 的一个序列（x 是 [0,k) 中的任意整数）后，这个序列不应出现距离 \ge 2 的逆序对。

也就是说，题目中的排序操作，可以改成跑一轮冒泡排序（检查相邻两项，若是逆序对则交换）！

重新模拟整个过程，不难发现它就等价于每次交换最远的一对逆序对，而且相同距离的逆序对互不影响。

现在引入拆分值域的思想。枚举一个 i，将所有 \le i 的值赋为 0，否则赋为 1，求出将 01 序列排序需要的排序轮数 F_i。答案即为 \max \limits_{i=1}^{n-1} F_i。

操作相当于每次将最右边的 1 和最左边的 0 交换，直到排好序。

考虑在序列上找到一个分界线，分界线左边的 1 的数量等于右边的 0 的数量，然后这些逆序的 (1,0) 对将会依次完成交换。

由于最终状态，不难发现分界线就在 i 和 i+1 之间。

那么求出 i+1 右边下标最大的 0 和 i 左边下标最大的 1 的下标之差（因为它们是最后一对交换的 (1,0)），这样就可以算出 F_i。

对 i 扫描线。后面的维护方法不再赘述。

时间复杂度 \mathcal{O}(n)（这里偷懒写了并查集，多了 \alpha(n)）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
    ll 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*10+ch-'0', ch=getchar();
    return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline void addmod(int &x){ if(x >= mod) x -= mod; }
inline void addmod(ll &x){ if(x >= mod) x -= mod; }
inline ll qpow(ll a,ll b){
    ll ans=1, base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod; b>>=1;
    }
    return ans;
}
inline ll INV(ll x){ return qpow(x, mod-2); };
int n,p[4000005],iv[4000005],L[4000005],R[4000005];
int fa[4000005];
inline int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
inline void merge(int x,int y,int p){
    x=find(x),y=find(y);
    if(!p){
        if(x>y) fa[x]=y; else fa[y]=x;
    }else{
        if(x<y) fa[x]=y; else fa[y]=x;
    }
}
void procedure(){
    n=read();
    for(int i=1;i<=n;i++) iv[p[i]=read()]=fa[i]=i;
    for(int i=1;i<n;i++){
        int pos=iv[i];
        if(pos>1 && p[pos-1]<=i) merge(pos-1,pos,0);
        if(pos<n && p[pos+1]<=i) merge(pos,pos+1,0);
        if(p[i]<=i){
            L[i]=i-find(i)+1;
            if(find(i)==1) L[i]=n;
        }else L[i]=0;
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=n-1;i>=1;i--){
        int pos=iv[i+1];
        if(pos>1 && p[pos-1]>i) merge(pos-1,pos,1);
        if(pos<n && p[pos+1]>i) merge(pos,pos+1,1);
        if(p[i+1]>i){
            R[i]=find(i+1)+1-i;
            if(find(i+1)==n) R[i]=n;
        }
        else R[i]=1;
    }
    int ans=n;
    for(int i=1;i<n;i++){
        ans=min(ans,L[i]+R[i]);
    }
    printf("%d\n",n-ans);
}