最小交换次数题解

题意：

一个长度为n的序列，相邻的两个元素可以交换，求最少交换几次才能使序列单调不下降。

思路：

不难想到一种纯粹的暴力方法：冒泡排序边排序边统计次数，时间复杂度O（n^2），40分TLE。

前置知识：逆序对——顾名思义，同一个序列内的两个元素，若元素1为a[i],元素2为a[j],满足1<=i<j<=n且a[j]>a[i]，那么称这两个元素互为逆序对。

有了以上知识，转换思路，因为当两个元素互为逆序对时，进行交换能且仅能消除1个逆序对，也就是——在确定交换能够维护序列相较于原序列更加有序的前提下，交换相邻元素，就是消除1个逆序对。****在不进行“垃圾交换”的前提下，交换次数就是逆序对的个数。 也就是说：最小交换次数其实就是逆序对的个数——— 那么题目就被转换成了统计逆序对的个数！ 那么接下来就很简单了————开一个“动态”的前缀和数组，怎么开“动态”前缀和的数组有很多（比如树状数组，哈希等），在此我建立了一个线段树维护一下逆序对个数的前缀和（因为线段树可以动态修改元素）

- 思路明确，废话不多说，多说不废话，代码如下：

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const long long maxn=1e5;//不开long long见祖宗
struct Node{
    long long l,r,sum;
}tr[4*maxn+5];
int b[maxn];
long long a[maxn+5];
void build(long long k,long long l,long long r){//建树
    tr[k].l=l;tr[k].r=r;
    if(l==r){
        tr[k].sum=0;
        return ;
    }
    long long mid=(l+r)/2;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[k].sum=tr[lc].sum+tr[rc].sum;
}
long long query(int k,int x,int y){//查询x至y区间逆序对的前缀和
    int l=tr[k].l;int r=tr[k].r;
    if(l>=x&&r<=y)return tr[k].sum;
    int maxx=0,mid=(l+r)/2;
    if(x<=mid)maxx+=query(lc,x,y);
    if(y>mid)maxx+=query(rc,x,y);
    return maxx;
}
void update(int k,int x,int y){
    int l=tr[k].l;int r=tr[k].r;
    if(l==r){
        tr[k].sum=y;
        return ;
    }
    long long mid=(l+r)>>1;
    if(x<=mid){
        update(lc,x,y);
    }
    else{
        update(rc,x,y);
    }
    tr[k].sum=tr[lc].sum+tr[rc].sum;
}
bool cmp(const int x,const int y){//b数组用a数组的大小排序，排编号（后面要查区间）
	if(a[x]==a[y]){
		return x<y;
	}//记得单独考虑重复的情况
	return a[x]<a[y];
}
long long n,ans;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=i;
    }
    build(1,1,n);
    sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++){
		if(b[i]!=1)ans+=(b[i]-1)-query(1,1,b[i]-1);//最好要特判（b[i]!=1），因为查询query(1,1，b[i]-1)时若b[i]==1时会死循环
		update(1,b[i],1);
	}
	printf("%lld",ans);//完美收工
    return 0;
}