以前一般用树状数组和线段树做这种题
这次换个思路试试，，归并排序！
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 111111;int n;int array[maxn];int tmp[maxn];LL ans;void my_sort(int l,int r){if(l == r) return;int mid = (l + r) >> 1;my_sort(l,mid);my_sort(mid + 1,r);int cnt = 0,i,j;for(i = l,j = mid + 1;i <= mid && j <= r;){if(array[i] <= array[j]){tmp[cnt++] = array[i++];ans += (j – mid – 1);}elsetmp[cnt++] = array[j++];}while(i <= mid){tmp[cnt++] = array[i++];ans += (j – mid – 1);}while(j <= r){tmp[cnt++] = array[j++];}for(int i = 0,j = l; i < cnt; i++,j++)array[j] = tmp[i];}int main(){while(scanf("%d",&n) != EOF){ans = 0;for(int i = 0; i < n; i++)scanf("%d",&array[i]);my_sort(0,n – 1);//for(int i = 0; i < n; i++)//printf("%d ",array[i]);//puts("");printf("%I64d\n",ans);}return 0;}
就是对虚怀若谷谦虚谨慎八个字真正理解的人，
