自动搬运

查看原文

来自洛谷，原作者为

	Diaоsi Enemy of God

搬运于2025-08-24 22:50:37，当前版本为作者最后更新于2024-03-27 16:49:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Quick Sort

感谢 @l_l 提供的证明。

首先证明快速排序的交换次数上界是 $\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;
}