题意分析

1. 问题本质：计算将序列通过相邻交换排序所需的最少操作次数
2. 关键观察：该问题等价于计算序列的逆序数（inversion count）
3. 逆序数定义：对于序列中所有元素对$(a[i], a[j])$，当$i < j$且$a[i] > a[j]$时，称为一个逆序对
4. 结论：最少交换次数 = 序列的逆序数

解题思路

1. 直接计算（暴力法）：

   • 双重循环统计所有逆序对
   • 时间复杂度$O(n^2)$，对$n=500,000$不可行

2. 高效算法：

   • 归并排序法：在归并过程中统计逆序数，时间复杂度$O(n \log n)$
   • 树状数组/线段树：离散化后统计，时间复杂度$O(n \log n)$

实现步骤（归并排序法）

1. 输入处理：

   • 读取序列长度$n$
   • 读取$n$个整数存入数组

2. 归并排序：

   • 递归分割数组
   • 合并有序子数组时：
     • 当右子数组元素小于左子数组元素时，累加逆序数（增加量为左子数组剩余元素数）

3. 输出结果：

   • 返回累计的逆序数

代码实现

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <vector>
#include <cmath>
#define endl "\n"
#define LL long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x); cout<<x<<endl;
#define lowbit(x) ((x)&(-x))
using namespace std;

/***
 * Author Informathons :
 * @author: 六月陌
***/

const int maxn=5e5+10;
const int mod=1e9+7;
struct node
{
    int num; //存数字
    int id;   //存初始位置
}a[maxn];
int c[maxn];  // 树状数组
int Index[maxn];  // 存排序后的位置(相当于离散化)
int n;
LL ans = 0;  //最终结果
bool cmp(node x,node y)
{
    return x.num < y.num;
}

void update(int x,int k)  //更新树状数组，在位置x加k
{
    while(x<=n)
    {
        c[x] += k;
        x += lowbit(x);
    }
}

int getsum(int x)   //查询从头到x的总和，也就是1的个数
{
    int res = 0;
    while(x>0)
    {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n == 0) break;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].num);
            a[i].id = i;
        }
        sort(a+1,a+n+1,cmp);  // 快排排个序就有了最终位置
        //↓↓↓ 记录每个元素的初始位置对应的最终位置 ↓↓↓
        Index[a[1].id] = 1;  
        for(int i=2;i<=n;i++)
        {
            if(a[i].num == a[i-1].num) Index[a[i].id] == Index[a[i-1].id];
            else Index[a[i].id] = i;
        }
        ans = 0;
        for(int i=1;i<=n;i++)
        {
            ans += i - 1 - getsum(Index[i]); // 放第i个元素的时候有i-1个，且getsum(Index[i])个元素不用移动 所以就有 i - 1 - getsum(Index[i])个需要移动
            update(Index[i],1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

逆序对板子题，不过会卡时间

int nw[N], tr[N];
PII w[N];

int lowbit(int x){
	return x & -x; 
}

void ADD(int x, int c){
	for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int SUM(int x){
	ll res = 0;
	for(int i = x; i; i -= lowbit(i)) res += tr[i];
	return res;
}


void solve()
{
	while(cin >> n, n){
		idx = 0;
		for(int i = 1; i <= n; i ++) tr[i] = 0;
		for(int i = 1; i <= n; i ++){
			cin >> w[i].x;
			w[i].y = i;
		}
		sort(w + 1, w + n + 1);
		ll sum = 0;
		for(int i = 1; i <= n; i ++){
			int id = w[i].y;
			sum += i - SUM(id) - 1;
			ADD(id, 1);
		}
		cout << sum << endl;
	}
}