看不懂？！

大概的意思就是：

给出一个长度为n的序列，然后每次只能交换相邻的两个数，问最小需要几次使序列严格上升

不断读入n，直到n=0结束

思路：

交换相邻的两个数，这不就类似冒泡排序吗？但是n<500000

算了吧，我回去颓A+B

于是我们就发现用冒泡排序直接计算次数是行不通的

但我们要知道：

冒泡排序的交换次数就是序列的逆序对数！！！

所以——就简单了吧~

如何求逆序对？

1、归并排序

思想是分治法

不断划分为两小段

然后依次由小序列合并为大序列，同时求出逆序数

2、树状数组

因为树状数组的修改查询是log级的所以可以使用（前缀和的方法），没学的建议先去学习一下，不是很难

Code：

#include
    
     #define ll long longusing namespace std;struct node{    int x,i;}a[500010];int n;int b[500010];int f[500010];ll ans;int read(){    int s=0;    char c=getchar();    while(!isdigit(c))        c=getchar();    while(isdigit(c))    {        s=(s<<1)+(s<<3)+c-'0';        c=getchar();    }    return s;}void update(int x)//修改{    for(;x<=n;x+=x&(-x))        f[x]++;    return;}ll sum(int x)//求前缀和{    ll res=0;    for(;x;x-=x&(-x))        res+=f[x];    return res;}bool cmp(node a,node b){    return a.x>b.x;}int main(){    int i,j;    n=read();    while(n)    {        ans=0;        memset(f,0,sizeof(f));        for(i=1;i<=n;i++)        {            a[i].x=read();            a[i].i=i;        }        sort(a+1,a+n+1,cmp);        for(i=1;i<=n;i++)//先hash一下,按数值给其标记，方便后面求逆序对            b[a[i].i]=i;        for(i=1;i<=n;i++)        {            update(b[i]);//一步一做            ans+=sum(b[i]-1);        }        printf("%lld\n",ans);        n=read();    }    return 0;}