题意：给出一个序列，求至少需要用到多少次操作，才能将序列从小到大排序。
思路：
数据量很大，n<500000，所以用冒泡模拟是超时的。 接下来就想到了求顺序数，总共需要交换的次数为每个数后面有多少个小于它的数的累加和。 如9 1 0 5 4，9后面比它小的有4个，1后面比它小的有1个，5后面比它小的有1个，总共为6个，即为答案。 求顺序数自然而然就是想到用树状数组。
但是这里有一点，那就是整数是0~999999999，数据太大，开不了那么大的数组。 由于n最多只有500000，所以最多有50万个不同的数据，所以将数据离散化减少数据范围。
用结构体存储数据最初的值value，以及一开始所在的位置idx，还有就是离散后的值ranks。 之后按值排序，从小到大开始赋值，最小的赋值1，然后依次递增。如果前后两个值相同，那么后一个赋前一个的ranks值。 最后再按照一开始所在的位置排序，从后往前赋值给数组a，a[i]的顺序数是前i-1个数中比a[i]小的个数，然后求累加和。 (按原来顺序赋值也可以，这样是求位于a[i]后面比a[i]小的个数的累加和，求的时候for循环从n开始递减)。
注意最后输出要用long long！！！
797ms，时间比别人长很多。。。
（不知道为什么，该代码在UVA10810 同样的一道题，竟然是WA。。。）
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn=500000; int a[maxn+10]; //存储离散后的数据序列，顺序是原来序列的顺序 int c[maxn+10]; //树状数组求和 int n; struct Node{ int idx,ranks; //一开始的位置，离散后的值 long long value; //最初的值 }node[maxn+10]; //按value从小到大排序 bool cmp1(const Node & tmp1,const Node & tmp2){ return tmp1.value<tmp2.value; } //按idx从小到大排序 bool cmp2(const Node & tmp1,const Node & tmp2){ return tmp1.idx<tmp2.idx; } int lowbit(int x){ return x&(-x); } void update(int value,int i){ while(i<=n){ c[i]+=value; i+=lowbit(i); } } int sum(int i){ int sum=0; while(i){ sum+=c[i]; i-=lowbit(i); } return sum; } int main() { long long data; while(scanf("%d",&n)!=EOF){ if(n==0) break; memset(c,0,sizeof(c)); for(int i=0;i<n;i++){ scanf("%I64d",&data); node[i].value=data; node[i].idx=i; } sort(node,node+n,cmp1); //将数据离散化 int num=1; node[0].ranks=1; for(int i=1;i<n;i++){ if(node[i].value==node[i-1].value){ node[i].ranks=node[i-1].ranks; } else{ num++; node[i].ranks=num; } } sort(node,node+n,cmp2); for(int i=0;i<n;i++){ a[n-i]=node[i].ranks; } //求顺序数 long long ans=0; for(int i=1;i<=n;i++){ ans+=sum(a[i]-1); update(1,a[i]); } printf("%I64d ",ans); } return 0; }