题解 P9673【[ICPC2022 Jinan R] Quick Sort】

· · 题解

Quick Sort

感谢 @_ll 提供的证明。

首先证明快速排序的交换次数上界是 \mathcal{O}(n\log n) 的，记 T\left(n\right) 表示对长度为 n 的序列进行快速排序的交换次数，可以得到如下递推式：

T\left(n\right)=T\left(a\right)+T\left(n-a\right)+\min\left\{a,n-a\right\}

根据对称性，不妨令 a\leq n\,/\,2，考虑这样的感性证明，将 T\left(n-a\right) 继续拆分，最终会形成大于等于 2 个小于等于 n\,/\,2 的部分并且花费了 \mathcal{O}(n) 的交换次数，由于这样的递归至多进行 \mathcal{O}(\log n) 层，所以 T\left(n\right)=\mathcal{O}(n\log n)。

有了这个结论这题就能直接做了，由于快排退化的原因，我们不能像伪代码里面那样用双指针找需要交换的元素。注意到确定主元（下标记为 p）位置之后我们只需要逐个找到 p 第一个大于等于 a_p 的值和 p 后第一个小于等于 a_p 的值，只需要维护区间 \max/\min 值就能进行二分了。

由于要支持修改，所以可以在线段树上进行二分。

根据上面的结论，交换次数至多 \mathcal{O}(n\log n)，单次线段树上二分的复杂度为 \mathcal{O}(\log n)，故总时间复杂度为 \mathcal{O}\big(n\log^2 n\big)。

Code:

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N=500010,M=5000010,INF=0x3f3f3f3f;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
int T,n,ans,a[N];
struct SegmentTree{
    int l,r;
    int dat,tag;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
    #define tag(x) tree[x].tag
}tree[N<<2];
void pushup(int x){
    dat(x)=max(dat(x<<1),dat(x<<1|1));
    tag(x)=min(tag(x<<1),tag(x<<1|1));
}
void build(int x,int l,int r){
    l(x)=l,r(x)=r;dat(x)=tag(x)=0;
    if(l==r){dat(x)=tag(x)=a[l];return;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void insert(int x,int pos,int val){
    int l=l(x),r=r(x);
    if(l==r){dat(x)=tag(x)=val;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)insert(x<<1,pos,val);
    if(pos>mid)insert(x<<1|1,pos,val);
    pushup(x);
}
int query1(int x,int L,int R,int val){
    int l=l(x),r=r(x);
    if(dat(x)<val)return 0;
    if(l==r)return l;
    if(L<=l&&r<=R){
        int res=query1(x<<1,L,R,val);
        if(res)return res;
        return query1(x<<1|1,L,R,val);
    }
    if(L<=r(x<<1)){
        int res=query1(x<<1,L,R,val);
        if(res)return res;
    }
    return query1(x<<1|1,L,R,val);
}
int query2(int x,int L,int R,int val){
    int l=l(x),r=r(x);
    if(tag(x)>val)return 0;
    if(l==r)return l;
    if(L<=l&&r<=R){
        int res=query2(x<<1|1,L,R,val);
        if(res)return res;
        return query2(x<<1,L,R,val);
    }
    if(l(x<<1|1)<=R){
        int res=query2(x<<1|1,L,R,val);
        if(res)return res;
    }
    return query2(x<<1,L,R,val);
}
int partition(int l,int r){
    int mid=(l+r)>>1,p=a[mid];
    int i=l-1,j=r+1;
    while(1){
        i=query1(1,i+1,n,p);
        j=query2(1,1,j-1,p);
        if(i>=j)return j;
        insert(1,i,a[j]);
        insert(1,j,a[i]);
        swap(a[i],a[j]);
        ans++;
    }
}
void qsort(int l,int r){
    if(l<0||r<0||l>=r)return;
    int p=partition(l,r);
    qsort(l,p);
    qsort(p+1,r);
}
void solve(){
    scanf("%d",&n);ans=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    qsort(1,n);
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}